How to choose between Lithium-ion vs NiMH batteries to power Arduino on the go.
Look at Battery University for many good ideas.

Both NimH and LiIon are viable for your application.

LiIon are easier to manage well if managed well.
ie do it right and they are easy to manage, but cut corners and they are easier to destroy.

NimH can be abused more with a slow degradation in capacity - although complete destruction is possible. 

As a LiIOn cell has a ~= 3.0V to 4.2V range you'd probably probably need a step up inverter with 1 cell, or a buck regulator with 2 cells, which is 'annoying'. If you are prepared to use the cell over say a 3.4V to 4.2V range with an LDO regulator for a 3.3V system then you lose a significant amount of available capacity but increase battery cycle life substantially. 

Nimh give 1.0 - 1.2 V/cell so eg   


6 cells give 6 - 7.2V for a 5V system,  
5 cells give say 5.25V - 7V if run down to 1.05V for a 5V system with a suitable LDO regulator, and
4 cells give 4 - 4.8V for a 3V3 system.   


NimH are easier overall to build half well and get half good results. 

LiIon are slightly harder to get going with in most cases, work very well if treated well, and are VERY unforgiving of bad treatment past a certain point.