PoW can be eliminated due to transaction fees alone not being enough to sufficiently protect a PoW network. Consequently, due to the electricity costs of mining, inflation through block rewards is needed.
The only possible solutions (as of now) are variants of PoS algorithms, as a staking node's cost of upkeep is dramatically lower than PoW.
There are a few aspects that can sufficiently incentive PoS consensus without the need for inflation:
1. Transaction Fees
1a. A percentage of all transaction fees should be paid to those who stake their tokens.
1b. A percentage of all transaction fees should also be "burned" (read: destroyed).
2. Token Value Incentive
2a. Token holders have the inherent incentive to protect their chain, because any meaningful attack would surely plummet the value of their tokens.
2b. Making it stupidly easy to do so would provide further incentives for them to do so through the use of features such as cold wallet staking.
2c. Making sure the coin has utility, so there is always demand for it on the free market, is another way of providing token value incentive. This can be done by ensuring the cryptocurrency provides a useful service or feature, for which fees are burned for providing.
2d. The combination of burning fees, making it easy to participate, establishing utility and ensuring there are no sources of inflation would create a sufficient amount of token value incentive.
3. Reducing The Amount of Participation Needed
3a. Reducing the amount of participants which are needed to secure the chain would make it further likely that no inflation would be necessary. For instance, with a dPoS-like PoS algorithm, only a handful of "volunteers" would be needed.
3b. Even if transaction fees are not very lucrative at the start, surely a handful of large token holders would still have enough incentive to "volunteer" due to token value incentive.
I am fully convinced deflationary cryptocurrencies will be the next big thing in the blockchain space, as they are an investor's wet dream. This is just a solution I have hammered out in my head recently, but I am sure there are other solutions. I am interested in hearing if anyone else has any other ideas to improve upon mine, or perhaps something completely different? I know @Anonymint has a solution of his own, but unfortunately we will have to wait to hear his idea.
Bitcoin inflates until year 2140 or so. Worry about this a little later.