Interesting ideas s, thx for sharing! A few comments below:
need a way to (1) generate scarce units of the currency and (2) prove that you held those units. To generate (or "mine"), any problem that takes processing resources to find needles in haystacks suffices;
If I understand you correctly, you propose that in this system a coin would be represented by a rare mathematical artifact. This is an interesting idea, but - and you might be aware of that - it's not how Bitcoin works. The Bitcoins themselves are just numbers associated with a Bitcoin address. Only the blocks, that secure the block chain, have the rare mathematical property. This distinction is important, because it means that coins can easily be divided into smaller units. If a rare mathematical artifact itself would represent the coin, then you would most likely not be able to divide it and thus would need much more of them. Maybe not an insurmountable problem, but I think it makes the whole problem of the rate of money supply a little trickier.
Speaking of the rate of money supply, I'm not sure how you would keep that under control in your proposed system. You say the difficulty of the process doesn't need to be static, but how is a change in difficulty decided and how can you reliably know what the current accepted difficulty is?
there's nothing to verify in any of these steps other than "has someone else spit into the public domain something that is a superior claim to spend this coin than that of the person who is communicating with me now?"
I don't find this whole "spitting things into the public domain" quite that trivial. Let's say you build a p2p-broadcast kind of system that Bitcoin has. An attacker could bring up lots and lots of nodes (IP addresses aren't hard to come by) and you might end up connecting only to nodes controlled by the attacker. The attacker is then controlling your perception of the "public domain" and can - for example - filter out those incidents where he already spent a coin that he is planning on double-spending at your store. Or do you think more of a centralized system to be this "public domain"? That would simplify it, but I would also consider a centralized solution as a disadvantage.