The design I'm working on will probably use two AA batteries. Two of them give you 2.4v at ~2000 mAh. Pretending your conversion to 5v is 100% efficient, that gives you around 960 mAh. That means you can draw 960 milliamps for one hour. Let's say our conversion is 70% efficient - it will likely be better, but that's a lower bound. That works out to be 672 mAh.

If we're powering a 100mA device, which is the most that low power USB devices draw, that's over 6 hours.

Modern switched-mode conversion can be done with one chip, one inductor, two capacitors, and maybe a diode and/or a resistor or two - a very small circuit. IMHO, it's really the direction to go if you're interested in portability. If you have a low power device and don't need too much battery life, you could even bring it down to a single cell.