But the problem is that the Voltage Regulator will apparently drain by itself too much energy from the battery (by heating), reducing drastically the autonomy.
So we would like to know if you guys can help us, if you can tell us exactly what (type of) regulator would be the best or if we need to find another battery.
You're getting a lot of options. What are some of of your other requirements? Cost? Size/package of the regulator? There are a ton of chips that do "step up" and "step down", which is what you want it seems.
Can you use surface mount parts or do you have to stick with thru-hole? If you can use surface mount options, there is a lot of "dc dc converters". You can borrow the design from the "Jeenode battery module", which uses LTC3525. It's a surface mount, draws 7-30uA of wasted current, accepts input voltages from 1V to 5.5V which is within your battery specs. It also has an output enable pin. Best of all, unlike many other dc-dc converters, the external components you need to add (input cap, output cap, inductor) are not as expensive as other dc-dc converters.
If you can't use surface mount components, try something like MAX756EPA. But this needs fancier capacitors and a zener diode.