Do you really need the linear regulator? Running the µC at full battery voltage will make things a lot easier. Besides, the regulator and the µC will always consume power, even in power-save modes, continuously draining the battery. Have a look at the data sheets and keep that in mind.
Because the ADC input (of a common sample-and-hold ADC, like that in an AVR µC) will only sink current when actually sampling a value, the transient low input impedance can be compensated for by simply adding a capacitor:

simulate this circuit – Schematic created using CircuitLab
The maximum sampling frequency will of course be limited this way since the capacitor will need time to re-charge through the large resistor before the next sampling is done, but I assume you will not be measuring more than, say, once a second anyway.
The time required to re-charge the capacitor can be set by varying its capacity and/or R1. Larger R1 = less "loss" of energy + lower max. sampling frequency. Smaller capacity will be charged quicker for a given resistor and so on.
You will want to maximize R1's value, and may then need to minimize the value of C1 to achive the desired sampling frequency.
The minimum capacity depends on the amount of charge the ADC will draw for a sample, which in turn is determined by the capacity of the ADC's sample buffer. For AVR devices I seem to remember that this value is specified in the datasheet. For other µCs I cannot tell, but the 1µF in the diagram will probably be more than enough in any case, and can possibly be reduced by a factor of 10 or so. The ADC's specs will tell.
Edit:
I found this in Atmel's datasheet for the ATmega1284p. The S&H buffer's capacitor is specified to 14 pico-farads, so a couple of nano-farads for C1 should be plenty.

See for instance the discussion here.