Viskr what calculation did you use to find the length of the charge?

Basically i=C*dV/dt, yes I know the current into a device won't normally be a current source, but we're doing back of the envelope calculations here, and it won't look like a resistor either

Assuming C = 1F, 500nA, gives you 1V decrease every 2,000,000 seconds. That's 23 days, to 2V, another 1/2V to 35 days. Pretty close to the calculator mentioned above, but this is just a rough number.

Personally I'd use a rechargeable Li (actually we routinely do). They are reasonably cheap, and the charging circuit is a diode and resistor to the 3.3V supply.

For the battery calculation it's the battery rating in mAh (mA hours) divided by the current. The ML2020 is a 48 mAh battery, so 48/0.0005 which is the 10 year number in the TI spec for that part.