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
Step 1: Connecting wires to the battery
Open up the cellphone and remove the battery to reveal the battery connectors. I also removed the SIM card. Examine the battery to figure out what terminal connectors on the cellphone go to the positive and negative terminals on the battery. Solder wires to these terminals. Don't worry about any third terminal, this is just a temperature sensor or something and is for the cellphone to worry about.