Here's a switching 5V regulator offered on ebay that will take anything up to 24V input and has over 90% efficiency:
http://bit.ly/tIUbd
The cost is $4 but unfortunately the shipping from Shanghai is $10. I think they were pulled from some other assembly line as some identifying info on the PCB is scraped off. It works as advertised.
Anyway, they're quite small and would fit in the pineapple easily and allow all sorts of battery options.
To take it a step further, there's a little trimpot on the regulator to allow the voltage to be adjusted from 1-10VDC, so it might even be used to supply 3.3 volts & bypass the fon's first regulator. That would improve the efficiency because a linear, non-switching regulator going from 5V to 3.3 volts is only 3.3/5 = 66% efficient.
There's a second linear voltage regulator on the fon that drops 3.3V to 1.9V for the processor (1.9/3.3 = 57% efficient) so maybe even a second one of these switching regulators might be used to advantage. Seems like most of the heat is in that area, so that's probably the bulk of the current draw. Maybe using two of these regulators is overkill, but I'd guess it would improve battery life overall by maybe double.
Looking at the size and function of this regulator, I wonder if they are meant to be used in a car USB power adapter (e.g. http://bit.ly/pc9OG). Maybe just cannabalizing one of those things would be cheaper, although it might be fixed at 5V and who knows what efficiency.