You should get a scope across a 0.1 ohm resistor in series with the module, and see what the actual current drain waveform looks like. Cellular systems are time-sliced, so a requirement for 700mA (peak) may be quite different to the 1 second average. Perhaps an 1000uF electro will be all you need.
Clever Li-Thionyl batteries are un-obtainium whenever you really need a replacement, I avoid them like the plague, unless they let you have a lifetime battery.
D cells have better $/J, and higher current than AA, if you don't mind the size.
75kJ - 21Wh, about 1/2 the cost of AA's here.
Varta D cells give energy at 11Wh@600mA or 20Wh@150mA, so probably D cells can run 700mA. (but you get twice as much energy from the battery if you keep the current down)
You could consider a small lipo battery that can power your radio, and float charged by a step up converter from 2x D cells, or even 1 x Dcell. In this case something like a 300maH lipo is acting as a cheap super-cap. It always gets recharged slowly by the low-current switchmode between cycles. Its capacity only needs to be small - you just need it to have good peak current - but this is exactly what lipos have.
You can recharge alkaline to a limited extent, especially if you never discharge it.
Assuming 20J per upload (3V,700mA,10secs), you could do 10 uploads a day for a year from 1 D cell.
For an outdoor application, a small solar panel may significantly increase the lifetime of the alkalines.
75kJ = 21Wh. At 250 sun days*5hrs/day, you need a 17mW solar panel to keep the battery charged. A 40mW solar panel is 1" square
Ah-ha! I hear you say, but won't this just make the switchmode division of TI rich? Well you can just use you micro for the very low current flyback convertors needed if you want.
In this case, software is generating the flyback convertor pulses, and using the ADC to check Vsolar, Valkaline and VDD, and thus do the regulation. The L1,D2 switchmode efficiency doesn't really matter. The L2,D3 switch mode efficiency does matter, so probably D3 should be schottky and the current kept low so Von of P1 is small.
The key here is that the currents are very low. If the transmit energy is 20J, the L2,D3 switchmode only has to deliver 2mA for 1hour to recover the energy (and the alkaline battery is only delivering 5mA). L1,2 are very small and cheap.
The voltage on a capacitor is proportional to the charge stored in it.
That means that as the device draws current, the voltage will drop. You have to decide how low is acceptable. Do the math.
For example, let's say the device can still run from 4.5 V. That means the capacitor voltage can drop 500 mV before the system doesn't work anymore. Let's use a 1 F cap as example.
(500 mV)(1 F) / (35 mA) = 14.3 s
That's how long a 1 F cap charged to 5 V can run your device at the worst case current draw.
Best Answer
This makes little sense. A power supply plugged into wall power can supply 250 mA indefinitely. A capacitor has a fixed amount of charge, and a even smaller amount of charge it can deliver usefully. In addition, the voltage on the capacitor goes down over time, since it is proportional to the charge in the cap at any one time.
You can't just "replace" a power supply with a capacitor. The two do different things, and are not equivalent.