PoW is merely a "thing to agree upon". You can choose any arbitrary thing or system to agree upon. Time, for example. Television programming line up. Sports scores. Bus schedule. Humidity fluctuations. Stock market changes. Or, anonymous electronic transactions. If you remove the money/greed aspect then it becomes waaaay easier to mitigate double transactions ("spends").
Think of a chatroom for example. That meets all the previously mentioned descriptors. Anonymous, electronic transactions of low monetary value. Now then, everyone participating in the chat room records an identical copy of all the transactions, right? So imagine if each time you reply to a specific user, you increment a unique sequential index. So to the recipient it looks like this: From Satoshi: @CCS hello fren! (Index #42)
Then when you reply to them the index is incremented, so they see from you: From CCS: @Satoshi long time no see, fren! (#43)
Since this little chain of incremental identifiers consists of only two parties, they will never run into many of the problems in an adversarial network. Each participant knows what next index is expected and if a message appears that deviated from that, everybody will know there is a problem.
Here we see everyone transacting independently without a third party and they are able to verify the order of transactions. If the transactions additionally included a sum (chksum), then each transaction would also be able to verify immutability. (error correction)
If one of my messages to you contains a PGP encrypted message containing my credit card number and a purchase order, then I have sent you an electronic funds transfer on a public distributed verifiable share ledger that involves no wasted PoW or mining nonsense.