5 year run time on small battery
This was going to be a comment, but I felt it ran too long, so I expanded it a bit more... some of you guys know me by now ;-)
This seems like a brilliant opportunity to include some energy harvesting methods, next to a safety backup cell to keep the proc active if all else fails.
If the measurement isn't complex you could consider buffering a couple, knowing your lithium primary coin cell will keep your core memory powered 99.999% of all possible cases, and reducing the number of busts of cell-power per year.
If for example you collect 32bytes of data every twelve hours and your proc has 2kByte, assuming you need 1kByte for other smart stuff, leaves room for 1000/32 =~ 31 measurements (I'm using the new, more pessimistic kibiByte here, but it should probably have been 1024 gives 32 measurements).
Now, if you're smart, you send them out in a bunch of 30 every 10 measurements and use your 1kByte memory as a 30 place ring buffer, always adding new stuff, but leaving every one of the last 30 measurements in memory. That gives you a lot of redundancy, while still only sending stuff 1/10th of the times you are planning now, gives 1/10th the power requirement over time. If you can then energy harvest that power back into a LithiumPolymer or LiFePO4 (more suited to sub-zero temperatures) cell, bang! problem solved. Small cell that recharges itself over time between transmissions.
For power harvesting you can look at solar, thermal or piezo or possibly many more, depending on the situation your system is in. (on land is a good candidate for a 1 or 2W solar cell, under water might be a case for hydro-powered, etc, etc).
Your battery setup could look like this:



simulate this circuit &ndash; Schematic created using CircuitLab
(I had to compact the schematic a bit to make the image turn out at least a little useful, so my apologies if some text crosses a few lines.)
If you do the maths right on the power use per x hours and minimum power gain per same x hours, you can potentially optimise the main battery down to a single 1Ah Lithium Ion cell, though I'd advise you go with a flat-pack LiFePO4, since they can also be discharged safely with pretty good capacity at temperatures below freezing. Still best to only charge them at +5 degrees Celsius or above, since it's a Lithium chemistry.
Of course, if charging is not at all possible in any way, the only solution to the battery is what Spehro suggests: Big ass Lithium battery with good quality.