I'd say best bet for any battery powered Arduino project would be a portable usb charger (the types used for charging phones). That way you're not wasting power using the arduino's voltage regulator. Also as they are often designed to charge two devices at once they can generally deal with a good couple of amps draw.