All sorts of "extended battery packs" and "emergency chargers" with USB output are starting to appear on the market, and they ought to be capable of providing an arduino power via the USB port (no 9V, though.)
Here's one currently one sale for $20. 2000mAh in a pack not too incompatible with the arduino form factor: http://dealmac.com/lw/artclick.html?1,281140,918723