O arquivo /usr/bin/rebuild-gcj-db
está no pacote java-1.5.0-gcj
, que está nos repositórios do sistema Red Hat.
O fato de você não conseguir encontrá-lo provavelmente significa que sua assinatura Red Hat para esta máquina não está ativa. Dê à máquina um direito de assinatura e tente novamente.
Como alternativa, converta o sistema para o CentOS.