You could do that, and it would indeed be reliable, but you would not be able to get the full charge out of the battery. Whether or not that would be okay for you is up to your requirements for battery life time.
A linear regulator (often called LDO) can only deliver a lower voltage than its input. Think of it as akin to a resistive voltage divider and you get the picture. The 'LDO' part means that it is low-dropout, so the input voltage does not need to be much higher than the output voltage (but always higher). Maybe 100 mV higher. Depends on the LDO, load current and other factors. So when the battery voltage drops below 3.4V or so, the LDO will not be able to sustain a 3.3V output voltage.
Another downside of using a linear regulator is that there is a power loss equal to the voltage difference from input to output, multiplied by the load current. Additionally, this power loss will be dissipated as heat in the linear regulator, so if the voltage difference and/or current is too great, the part will become too hot and desolder or destroy itself. For the circuit you have described, heat is very unlikely to become a problem though.
Enter the buck-boost switching regulator, which can deliver a stable output voltage with either higher, equal and lower input voltage, AND does not have the resistive power loss associated with a linear regulator. Efficiency will still not be 100% though, it never is. You should be able to achieve something like 90% though. That figure varies a lot, both in datasheets and in real applications, as many factors play in. More importantly though, you will be able to run on the battery until it is empty of energy. Finding a buck-boost with 2.7-4V input range and 3.3V output will be no problem at all. Plenty of those exist for exactly the type of application you are describing, and exactly which one you will need depends on a host of other requirements.
Finally, you should not dischage the battery too far if you intend to recharge it. Choose a buck-boost with UVLO (under voltage lock out) and set the resistor divider to disable the regulator around 3V. There is little to energy to be used anyway once the voltage has dropped that far. Take a look at a discharge curve and for the battery to help you choose the exact voltage.
http://www.powerstream.com/z/LG-18650HE2.png
In your place, I would either:
1. Use an LDO if there is not really a need to optimize for battery life time.
2. Find a buck-boost regulator already soldered to a small PCB with all the external components. You can get something like that on eBay. Just be sure to check the various requirement, like voltages and output current.