Making a power supply that offers two voltages
A 7805 should be able to regulate 5 V so long as you keep the input above 8 V or so. Dropping a 12 V battery to 8 V sounds like quite a drop to me, but I don't know the full parameters of your batteries, etc.

Supposing that a drop below 8 V is possible, the easy solution is to find a regulator that doesn't need so much drop-out. There are low drop-out regulators that can regulate 5 V with inputs as low as 5.3 or 5.5 V. The trick will be finding one that can also handle the power needed to regulate 5 V when the input is as high as 12 V. Since you haven't mentioned the amount of current being sourced, I can't say whether this will be a problem or not.

A less easy but much more efficient solution would be to use a switching regulator. A buck regulator could probably be found that will be able to regulate 5 V with inputs between, say 6 and 24 V (obtaining good performance with very wide range of input voltages may require some careful design and design trade-offs). These can even be found with physical size and pin assignments designed as direct replacements for the 7805. A buck regulator will also dissipate much less heat than the 7805 when the battery voltage is high, so this could save you in other ways.

Finally, if you think the input voltage might dip below maybe 5.5 V, and you want the efficiency of a switching regulator, you can look at buck-boost circuits. A buck-boost could conceivably generate your 5 V mcu power supply given an input voltage anywhere from 1.2 to 12 V. 

The details of choosing or designing any of these circuits requires knowing the range of currents your circuit will draw, and the range of input voltages you need to accomodate.