Normalmente, se usa por questão de desempenho arrays de tamanhos estáticos suficientemente grandes, como 999 células. Ainda assim, em C++ tem um recurso de alto nível: fluxo (stream). Fluxos permitem adicionar valores aos poucos, sem preocupações com o tamanho (fora o suporte da arquitetura). O uso da classe `stringstream` (na biblioteca `<sstream>`) permite formar e depois gerar uma estrutura `string`, esta podendo ser vista como um `const char*`.

Em C, acho que stream teria que ser implementado a mão. Há várias formas de fazer isso. Outra opção que você tem é controlar o tempo de vida dos dados, inclusive usar blocos para limitar o tempo de vida de variáveis locais. Assim, pode criar um array de tamanho assombroso, copiá-lo para um menor e apagá-lo. Assim, por exemplo.

    # include <stdio.h>
    # include <stdlib.h>
    int main( int argCount , char **argVector ){
       int tamanhoDoNome , indice ;
       char *nome ;
       {
          char nomeTemporario[999] = {0} ;
          cout << "Informe seu nome completo: " << endl ;
          fgets( nomeTemporario , 998 , stdin ) ;
          for( tamanhoDoNome=0 ; nomeTemporario[tamanhoDoNome++] ; ) ;
          nome = malloc( tamanhoDoNome*sizeof(char) ) ;
          for( indice=0 ; indice<tamanhoDoNome ; indice++ ) nome[indice]=nomeTemporario[indice] ;
       }
       // Agora não existem mais nomeTemporario e suas células, ficou nem a carcaça de sobra.
       free( nome ) ;
       // Agora não existem mais as células de nome, só existe a variável, ficou só a carcaça!
       return 0 ;
    }

Alguma dúvida?