If the LiPo solution doesn't appeal, then four NiMH or NiCd cells produce a nominal 4.8V and it seems quite common to run an Arduino off that. An unregulated source like that probably wouldn't be suitable, though, if you were also supplying external loads from the same batteries which were high enough to impact the battery voltage, since this would then tweak the Arduino supply voltage each time you switched the load on or off.