Fona808 + arduino micro; all from battery

Hi,

Micro needs more or less 5V to work.
Fona808 goes with 3,7V battery socket, and it can work on both logic levels 3 or 5V.

I am thinking how to get it working from single and huge battery (micro + fona at the same time) without external power supply, except for charging.

I have no practical solution for several days now so I ask, maybe you will have something on your mind