If the worry about raising the block size will increase centralization,
could not one could imagine an application which rewarded decentralized
storage of block data? It could even be build aside or on top of the
existing bitcoin protocol.

See the Permacoin paper by Andrew Miller:
http://cs.umd.edu/~amiller/permacoin.pdf

Regards