¿Y a char *tmp que tamaño le damos? Estamos en la misma y usando memoria dinamica dos veces para nada ...

Yo lo haria mas o menos asi:

void getString(char **pstr)
{
  char tmp[16384];
  fgets(tmp, sizeof(tmp), stdin);
  *pstr = (char*)malloc(strlen(tmp) + 1);
  strcpy(*pstr, tmp);
}

Primero reservas memoria para los punteros y despues con un bucle llamas a esta funcion pasandole la direccion de cada elemento del array de punteros a char.

Muchas gracias por todas las respuestas, siento no haber podido contestar antes, he estado de exámenes y he tenido problemas con el ISP de internet y por eso no lo hice antes, ya por suerte se ha arreglado todo.

Tu idea de la variable temporal la tendré muy en cuenta, realmente si pongo un numero muy grande no creo que una cadena llegue a tener mas de ese numero y luego con realloc podría disminuirla a lo que ocupa la cadena.

Una pregunta, la idea de leer carácter por carácter es mas lento que el algoritmo propuesto por Eternal Idol de la variable temporal?

Y una ultima cosa, realmente la cadena en C no se almacena hasta que se pulsa enter, ¿no hay una forma de que cuando pulse enter todo lo que este en studin o en la entrada de datos que internamente el sistema operativo administra sacar los caracteres que han sido leídos en esa entrada y con ese tamaño darle el valor a la cadena?

Un saludo y gracias de nuevo.