..so I can't directly use a lipo, I already thought about that...
Why not? Do use lipo and a very low drop voltage regulator, for example LE33CZ (through hole) or MCP1700/3V3. Lipos runs from 4.2->3.5V and those regulators need 0.2Volt drop to be happy, so an ideal solution..
I am using MAX1724 (3V3 and 5V) step-up with my few designs as well..