How to measure battery charge and depletion over time
It's better to measure charge in and out to determine charge state. You can get ICs that do this for you, e.g. http://www.ti.com/product/bq27000 : it works by having a tiny ammeter connected on the output of the battery pack.

It's usually possible to determine "fully charged" from the EoC "end of charge" conditions of the battery, and the charging logic must make this decision to stop charging.

Lithium battery chemistries do not like being completely discharged; usually the battery pack has extra circuitry that disconnects it at a particular voltage drop. The ones I've been using do this at 2.8V. 

The variation in voltage from "charging" to "fully discharged" is just something that you have to design for. Usually there will be a buck/boost converter that turns the actual battery voltage into a steady 3.3V or whatever voltage is needed for the logic.