[Note: I have modified / improved the suggestion in subsequent comments, scroll down to see my later ideas]
PoW is useless and wastes energy. Let's replace it with useless tokens.
This is not a joke.
You want Nano to be feeless at any cost. Alright, got it.
You want users at countries where 1 cent is not considered disposable change to be able to use the service without worrying about fees. Got it.
Many of these users only have mobile phones (and probably not very fast ones) that wouldn't be able to compute PoW. So your solution is to compute it and gift it to them (I'll ignore for now that this kind of service is highly susceptible to abuse).
So instead of donating useless computing power and electricity (which costs money and causes carbon emissions), why not donate useless tokens instead?
Design tokens that can't be used for anything other than as a burnable "gas" for performing a transaction. One token = one transaction.
Now you might think: Everything has value. These tokens would be traded eventually.
I'm not a finance person (more of a computer science person), but I don't think anything is impossible. Let's try to shift the effort for a minute from things like memory hard PoW and precomputed attacks to considering the idea of a token that is useless by definition - the only thing that it can do is be burned to perform a transaction.
This should be the worst possible token for investors: infinite supply, arbitrary price decided by software, not tradable anywhere, could lose its entire value at any second. As useless as tokens in a theme park that's in the process of filing for bankruptcy.
This shouldn't be that hard?
Here are some ideas: the token will be materialized by burning a small amount of Nanos to some predefined bogus account. The token will have versions like v1, v2, v3 etc. that would increment with software upgrades. Once the version is upgraded, all the tokens of versions one before the current one would become completely useless (for example upgrade form v2 -> v3 causes v1 to become useless). Tokens cannot be traded between versions. This means the tokens would have to be bought only for short-term use.
I haven't spent a lot of time in considering the specifics of this kind of idea, but I think people with different backgrounds than mine (like finance and economics) could easily come up with even better solutions. As a technical person I understand the development cost of implementing a secondary "balance" (albeit it would only be a simple integer, 4 bytes suffice) but I want to put that aside for now because I believe the effort would certainly be worth it if it proves to be effective.