maybe use an ldo regulator to keep the battery voltage as close to 5v as you can
Eek, no! LDO (linear) regulator + battery = flattery.
If you want your battery to last, you need a switched mode regulator circuit.
Instead of the, say, 25% efficiency of an LDO, you'd have nearer 80% or more with a SMPS.
You could easily use a car cigarette lighter -> USB adaptor. That will give you a good 5v with little power wastage. Most of the chips they use handle between 7.5v and around 70v as an input.