Observar um personagem como gênio é bastante relativo, então vou me focar apenas em personagens que demonstraram alguma condição de superioridade intelectual ou prática desde a infância.
Concordo com todos que você citou com exceção de Konan e Fugaku. A primeira não fez nada de mais além de dominar um Hijutsu(algo que praticamente todo shinobi pertecente a algum clã possui). O segundo não me lembro de ter nada mencionado sobre alguma capacidade excepcional desde a infância.
Eu adicionaria:
Gaara - Ele ja era um gennin com capacidade de enfrentar Chuunin's e até Jounin's, se tornou Kage muito cedo justamente por ter se tornado extremamente forte muito cedo.
Tobirama - Desde a infância ja era linha de frente do clã Senju, conseguiu perseguir e descobrir o relacionamento de Hashirama com Madara sem deixar seu irmão perceber, ja tinha maturidade o suficiente para entender que a guerra contra o clã Uchiha era besteira e na infância ja vislumbrava um sistema diferente junto de seu irmão.
Nagato - Este é meio óbvio, ja compreendia os 5 elementos da natureza desde criança.
Obito - O caso dele foi um pouco tardio pois ele foi desabrochar apenas após ter sofrido o acidente. Mas em uma jovem idade ele ja estava controlando o Mokuton muito bem, controlava a Kyuubi, dominou perfeitamente o Kamui e estava invadindo Konoha.
Tsunade - Desde a sua infância ela ja conseguia concentrar chackra nos punhos e garantir sua super força, até o próprio Hashirama conhecia sua força.
Hashirama - Nem preciso explicar.
Madara - Nem preciso explicar.