I'm fairly certain the onboard 3.3 volt regulator is a cheap linear one and will need at least approximately 3.8 volts on its input before it starts regulating.
To answer the original question, I would suggest 4 AA or C NiMh cells in series giving around 4.4 to 5 volts which will be ample for the 3.3 volt regulator and will probably be OK for most USB devices. Holders for these cells are readily available eg http://www.maplin.co.uk/aa-siz.....ders-31427
Or for guaranteed to work, put 6 in series and a 5 volt regulator. Heat sink on the regulator advisable.
AA size gives around 2500 mAH. Chargers are readily available.
In emergencies when the NiMHs are flat and cannot be recharged, disposable alkalines can be substituted.