I think the solution is some sort of PoW gateway like people are setting up now. Or a micropayments system where each page request costs a fraction of a penny.
You could combine that with some sort of IPFS/Bittorrent like system where you allow others to rehost your static content, indexed by the merkle hash of the content. That would allow users to donate bandwidth.
I really don't like the idea that you can get out of this by surveiling user agents more or distinguishing between "good" and "bad" bots which is a massive social problem.
Nobody wants proof of work, leave the block chain inspired nonsense to the crypto children
This is the original use-case for proof of work though. The idea of using proof of work to hinder spam dates back to 1997[1]
[1] https://en.wikipedia.org/wiki/Hashcash