If you want a rechargable battery pack, LiPo batteries are a possibility and so are AAA or AA sized
NiMH batteries. Sealed lead acid batteries (these are usually gel based, unlike automotive batteries) would also be an option, except they would probably be too heavy and bulky for what you have in mind.
However, the most important consideration for any battery pack will be the total voltage the pack supplies. Each battery (it doesn't matter if they are rechargable or not) will be rated based on a nominal voltage, but the actual total voltage at any given time will vary based on charge level. The exact details will depend upon cell chemistry, but a fully charged cell could have an actual voltage 10% to 30% above the cell's nominal voltaged and a mostly discharged battery will be well below the nominal voltage (50% less or more).
Since the nominal voltage of a cell is centered on the range of charge levels where the voltage change is most linear and usually the smallest; it's best determine the total number of cells primarily based on the nominal voltage as this will yield the longest working life for the battery pack. Yet it is also a good idea to ensure that fresh batteries don't provide too much voltage to what you are trying to power. You don't mention which Ardunio you plan to use, but if it's one with an on-board regulator that will simplify things if the battery pack's total nominal voltage is over ~7 V
DC. If not, or you to bypass the regulator reduce the power used, then you have to make sure the battery pack's maximum voltage isn't potentially harmful to the microcontroller. For example, the ATmega328P used on the Uno the absolute maximium voltage you can power it at is 6 V
DC. Finally, I've read that for the latest versions of the Uno it's not recommended to bypass the voltage regulator unless you have a very stable 5 V
DC source.