The problem with proposing centralization as a solution, is it simply doesn't scale in terms of ecosystems, for the same reason that closed source doesn't scale but open source does.
I'm not saying that "centralisation" is the solution. That said, in a rigid set of rules, *whatever they are*, centralisation will happen, no matter what system of rules is used, because of economies of scale, and because of divergence of any formula which has something at stake.
The thing is that calling PoW intrinsically centralized *because of storage and bandwidth* is, in my opinion, totally misguided, and proposing as a solution the hardcoded limit of functionality (in bitcoin, the number of transactions per second, as long as it is ridiculously small as compared with the potential market) is way, way worse than allowing the solution to scale according to technological limitations, which will remove themselves as technology advances. No rigid set of rules should include hard limits on technology use, like Bill Gates did.
As such, of all reasons, PoW is NOT intrinsically centralized because of storage and bandwidth limits. At the moment, bitcoin is centralizing, because of economies of scale which are SO HUGE with asics, that CPU/GPU mining is out of the question.
I agree with your statement of principle that any algorithm can be ASIC-ed, but the cost to do so, and the gains obtained can push this transition to the future. The point is that this transition should be enough in the future for the coin to have a reasonable life time, and in the end, be obliged to fork and to become worthless.
My idea is that the only solution to avoiding centralisation, is modifying the rules regularly and having complex PoW mining, so that too big investments, for instance in ASICs, are too much at risk, so that the step to large economies of scale is always beyond the time line when the algorithms change. There's a natural way of doing so, with continuously creating altcoins, that take over the "old" mature coins ; this could in a way be formalized by having finite block chains (that is, block chains that will only live a finite amount of time, say 10 years) and continuously forking. The point being that a block chain that centralizes, is supposed to lose its value, because it loses its potential immutability. The day that 60% of bitcoin mining is done by 1 entity, bitcoin will be worthless in principle. So it is in a coin's long term viability that centralisation is to be avoided.
Another solution can be to have an inflationary pressure as a function of centralisation, in other words, a non-linear relationship between PoW and mining reward: this is a kind of transition from PoW to a diverging PoS. The diverging PoS is necessary so that an inflationary bomb explodes when PoW gets too centralized ; in other words, the opposite of what happens in the ethereum time bomb. As such, a centralizing coin destroys itself by hyper inflation, pushing people to a less centralized coin. Instead of allowing wealth accumulation through centralisation, a coin should be designed so that it gets more and more worthless, the more it centralizes, instead of impossibly fighting centralisation.
The only solution to avoid centralisation, is regular "rule revolutions". Like in real life, where war, revolutions, unforeseen events kill successful companies, and nations, so that centralisation has been avoided up to now. We are leaving a dangerous period where centralisation in the USA was a danger, but as we see, the rules get overthrown, and the world is again diverging from centralisation, with enough wars, conflicts and uncertainty.