Bom, não encontrei nada que diga o contrário, mas parece que pode ser usado o realloc sem antes usa malloc.
Além é claro que deve existir alguma razão para usar malloc em vez de realloc.
PS. Estou fazendo um apetrecho com um atmega8 então todo espaço no screch que eu puder economizar é bem vindo, então, pretendo não inicializar um array de array dinâmicos com malloc (que será executado apenas uma vez) e depois ter que ter as chamadas para os realloc para aumentar ou diminuir o tamanho do array.