If the mining reward was suddenly changed to 0, and there were no mining fees anymore, what would happen with the Bitcoin network? Assume there is another anti-spam measure in practice (ex: a tx would need the last block hash + some small PoW on top of it). Would Bitcoin suddenly collapse and get unusable, would it still operate normally due to voluntary mining?
Even though they are still somewhat negligible to miners today, transaction fees play an important role in the protocol known as Bitcoin, and will play an increasing role in the future. Just look at all the questions this SE site gets about unconfirmed transactions. Asking how the protocol works when removing all direct mining incentives is redefining the protocol in a major way. It's like asking how HTTP would work if you remove the verbs from the protocol. At that point, it's something completely different.
When you remove such a critical part of the protocol, it's difficult to replace with something that works. For example, your proposal of doing a proof-of-work on top of the last block hash as part of the transaction will effectively break the ability to use the protocol for smart contracts.
You are essentially asking what happens if you remove critical parts of Bitcoin, but still use the basic idea rather than creating a new protocol to match your paradigm of no mining rewards. To that, I can only speculate that such a system is doomed for failure.