The suggestions so far imply you have two options:
1) Use a linear regulator, dissipating Vin-Vout as heat
2) Bypass the regulator by dropping 100% of unregulated Vin through device
A third option would be to use a switching regulator. Boost converters produce higher voltage at the output than the input and, therefore, require a higher current at the input than the output which none of the batteries described above should have an issue supplying. I didn't pull the datasheet for your specific component, but there is probably a drop-in (package- and pin-compatible) switch-mode equivalent for it requiring few or no external components.
Depending on your sensor refresh rate, a rather tiny solar cell (if sunlight is available to your device) could power the boost converter and run the device for "free" while simultaneously charging a super-capacitor to power the system through the night until morning. Two supercaps in parallel would approximately double your run-time without input power. I suspect that a couple of supercaps could potentially run your setup for many days between power applications, but you could also just substitute an appropriate rechargeable cell if you want to guarantee power for longer periods. The boost converter will (slowly) float the cell back to full all day long as long as there is enough sunlight.
These aren't spec'd especially for your application but to give you some ideas:
These are extremely tiny: https://www.sparkfun.com/products/9962
Since I didn't sum your power requirements, this is possibly too extremely tiny to even parallel cost-effectively for your purpose; in that case, select one slightly less tiny. :)
DIP8 step-up/down: https://www.sparkfun.com/products/317
1F, 2.5V supercap: https://www.sparkfun.com/products/10068
Two in series would make a 0.5F, 5V backup.
10F, 2.5V supercap: https://www.sparkfun.com/products/746
Linear also makes a thousand different families of power-management chips. Many are SMPS's at heart, but come equipped with a variety of handy features like output-enable, reverse-polarity protection, brown-out/low-power detect, redundant battery fail-over and/or backup power supply, load balancing, balanced battery charge and/or discharge, over-current protection, etc, etc... You should be able to find the perfect chip very quickly using their parametric search.