Old cellphones are easy to acquire and they have built in lithium charging circuitry. What a wonderful base for a power supply for small mobile things. I hooked up a cellphone to the arduino with the ability to charge the cellphone when you plug the arduino into the usb port. Please note that this was just a quick rig and as i did not have the correct screwdrivers, does not involve taking apart the cellphone. I'm sure if you have access to the correct screwdriver you wouldn't have to cut the cellphone charging connector and could just solder wires directly to the charging terminals. Sorry about the image quality I made it in between college classes and so i took pictures with my laptop's webcam.
You will need:
an old cellphone (must use 5volts as its wall wart charging voltage)
some cellphone batteries (optional, minimum one)
wires and a diode
the cellphones wall wart charger
a connector of some sort to plug into the arduino (i cut a chip socket in half for mine.) Minimum of 3 pins