I always start off my posts here by apologizing because I am very non-technical, so once again, sorry. This is probably somehow completely wrong but here is a wild idea.
What if you decoupled awarding coins from solving blocks and instead distributed them on the basis of a stochastic function regarding the computing power being contributed to the network. With the same distribution timeline, just not "necessarily" to the node who just submitted the next valid block.
Wouldn't this still provide incentive to mine and contribute with the most computer power possible but never allow planning for a double spend?
If you then somehow completely cloaked or made anonymous where the solved blocks were originating there could be no double spend.
I think then there would also be no reason to keep the whole chain.
You could truncate after 20 blocks or something and have more built in transaction anonymity?