Well, almost everyone has a PC.
PC usage is "decentralized" and we are not all using dumb terminals, which was envisioned in 60ies and 70ies.
I think that BTc/whatever coin decentralization is possible along the same line-a coin that has strictly CPU (not even GPU) algorithm without scaling.
I would think that it should be possible.