I just got a 1500mah rechargeable battery. Has solar charger on it too. About 9.5 x 4 x 1.25 cm. Just a bit bigger than a Nano. They build it in basically the same case as a Chipod.
Many Chipods have 270mah batteries. With this add-on, I would expect to get over 5 times the amount of run time. Since it has a solar cell on it, it could run a heck of a lot longer. Has cool LED flashlight. Uses the same AC adapter and usb cable as chipods do.
I got it on ebay for $13 including shipping http://search.ebay.com/search/search...+Solar+Charger
It charges my Razr phone and my thumb drive mp3 player.

If you make a battery pack from 4 rechargeable batteries, you probably won't need a regulator. NiCad and NmHd are about 1.2V each. 4 x 1.2V = 4.8V Close enough to 5V

A regulator wastes a lot of battery power as heat.