Supercapacitor Voltage – Risks of Draining Below Minimum Voltage

I simulated your circuit using LTSpice for 3V in and 4.2V in and there was virtually zero overshoot. That means you could use 6.3V capacitors. If your local supplier doesn't have any you can always order offline. You could probably get 10V caps just to feel safe and increase the robustness of the circuit if area and cost aren't super critical to this design.

1. That cap has a leakage quoted as

0.02CV (uA) or 3mA, whichever is smaller, after 5 minutes at20C. Where I = Max. leakage current (uA), C = Nominal capacitance (uF) and V= Rated voltage (V)

So for a 6.3V 4700uF cap, the leakage would be 592uA, which is much smaller than 3mA, but still roughly 100x the circuit's standby power consumption, which does seem a bit sad.

2. Yes, there are lots of caps specifically made as 'low leakage' - obviously that can be a bit like 'low cost', in that it's relative to someone else's expectations, but you can do much, much better than a generic electrolytic. There are also caps made specifically for what you're trying to do here, called 'supercaps' or 'ultracaps' - they're so big and give such long retention times at your low microamp currents that you could probably get rid of your second battery. Here are some supercaps which have very low leakage: http://www.maxwell.com/images/documents/hcseries_ds_1013793-9.pdf

3. Yes.

4. Use a more suitable cap, see above.

A general note about doing low microamp-level microprocessor projects - you have to be really very careful about everything to get down to that sort of level, and even trivial mistakes with a single pull-up turned on in a micro, or a carelessly chosen component can leave you absolutely orders of magnitude away from where you need to be. You need to make sure you have the kit to make trustworthy measurements of low current.