I realized that while the USB-module is a piece of cake as there is USB power available, I have no such luck with the wireless module. So I need to figure some way to power the ESP-12F module and the level shifter. Couple of alternatives that came to mind:

• USB-power. I could use one of those power-banks and get 5V power. I can power the level shifter directly from 5V rail, but I need additional conversion to get 3V3 for ESP-12F. LDO would be simplest, but might be too inefficient (66%). It's bit hacky to use USB for power without any negotiation etc, but I hope that will work anyways.
• Lithium cell. Maybe 18650 (quite big, and I don't have any at hand), or find some nice small pouch cell somewhere (where?). Simply LDOing it down to 3V3 or maybe 3V0 could work fine, as both level shifter and ESP are specced for 3V0.
• 3-4xAA. Somewhat bulky, but the most readily available solution. With four cells, I could drain down to 0.8V and still get 3.2V which should be enough. Again, LDO might be too inefficient, but I wouldn't be too concerned. Probably would make sense to add some extra capacitance (how much?) in the power rails to help feed the peaky consumption of ESP.

Ideally I'd have power port that would accept anything between 3-6V, and convert that efficiently to whatever I'd need. For first revision, I'm kinda tempted to just throw a decent LDO in there and then add proper SMPS on later. It is somewhat questionable how much "real-world" use this will ever see anyways, so it should be fine. Besides, 2000mAh should last for something like 5 hours even with just LDO, so that doesn't sound that bad.

I will want to have some under-voltage protection to prevent brown-outs etc, even if I'm using protected cells or batteries that don't care.

A random reddit link that might be useful: https://www.reddit.com/r/esp8266/comments/4gmkfl/how_to_actually_run_an_esp8266_for_months_on_aa/