Something else to consider are the radio controlled helicopter/aircraft LiPo batteries. Extremely high energy density, slow self discharge rate, and come in various voltages (mainly 7.4V and 11.1V though). Though you do need a specialised LiPo charger and of course if they get punctured they tend to burn/explode very violently.
Actually, yes, you're probably better off with NiMH