You can get an emergency USB charger at the dollar tree (or online at their website). It takes 2 AA batteries and outputs 5V. It also works with 1 battery. You can rip it apart or just solder onto its connections directly to power an Arduino with 1 D battery.
I don't know how efficient it is, as I haven't measured the current. And the Arduio isn't that efficient from what I understand, but this should work for stand-alone projects that use just the processor. I bought a case of 24 of the chargers for some ATTiny projects I'm thinking of doing.