A proof-of-work or proof-of-stake system are the only known ways to stop someone from running a lot of client peers or hatchers in a decentralized system in order to block transactions or double-spend. I do not see any new solution to the Byzantine Generals problem in your answers.
What about a "unique node list"? As employed by Ripple.
https://ripple.com/wiki/Unique_Node_ListI'm also thinking there must be a way to mathematically achieve "proof-of-verification", ie. a type of proof-of-work that is less random, and has more utility toward making the system honest. ie. the work done to verify a set of transactions results in a mathematical proof/signature, that can be verified by other nodes. If one of the nodes finds out that you did not do the work (ie. tracing the transactions to that point shows an invalid transaction, or mathematical derivation is incorrect), then your node gets penalized or ignored.
That's precisely what our method attempts to achieve.
There seems to be some stigma about the method we are developing, but I haven't at one point said that it's unbreakable, it is,
IF you have enough resources to pull it off. What our algorithm and network architecture should achieve (and we'll soon see if it really does in the beta) is more resiliance.
The network as a whole trades some efficiency for security of verifying the transactions almost exactly as you state.
Lots of new posts in here today, so I'll trawl through and pick out any other interesting ones and reply over the course of the evening.