Yeah its not going to be a very frequent use project tbh so the 9v solution should be fine, I might consider using 4 aa's at 6v but I'll see where the 7805's dropout voltage kicks in first.
Or you can look it up...
http://www.fairchildsemi.com/ds/LM/LM7805.pdfPage 3 indicates an LM7805 requires at least 2V (7V input) to stay within specs.
One could use two typical diodes in series on the output of the 7805 regulator chip to drop the voltage to 3.6v.
I've always thought that was a bad idea. At very low current draw, the diodes don't drop as much voltage. Having a power supply voltage that changes under load just seems like such an unnecessary thing, destined to cause odd problems at a later point.
OK, here I go, flogging the MC34063 again... There are newer switchmode regulator chips, but this one is ultracheap, comes in DIP and SMD packages, and has several design tools out there. You will need to start with more than 6V, but you aren't wasting so much power.
I favor this particular MC34063 calculator. Watch out for negative values in the answer, that signifies that what you are asking it to do, cannot be done.
http://dics.voicecontrol.ro/tutorials/mc34063/