Most cellphones and PDAs can be recharged from the USB port of a computer. All you need to carry is the appropriate cable. These people specialize in them: http://www.ziplinq.com/ . They also sell tiny transformers that plug into the wall (or a car) and deliver power to a USB socket.

The cables are light and small. You can plug them into your own laptop, or someone else's.