You don't need the government, you need the society at all. These things can be done in a lot of ways, all them compatible with a trusted ledger that keeps track unambiguously of who owns what.
Notary services were for a long time independent of the State, they may still be in some countries and places. This is indeed something in which a global decentralized trusted ledger can help.
See my "property ownership == enforcement" comment above. If you yourself are enforcing your monopoly over your property - you can stick a sign outside your front door saying "trespassers will be shot" and be done with it. If it's a militia, have them do whatever they think is reasonable notice. If you're depending on your local community, stick it on a community noticeboard.
The question is, exactly why do you need a trustless ledger in order to post notice that you're willing to enforce your monopoly? What problem, precisely, does a blockchain solve?
You don't need to solve every problem to solve some problems. Blockchains don't address enforcement for real property. They do address everything else. And everything else is a big deal.
I don't think they do address everything else - or rather, I believe that if you have to trust an entity for enforcement, you have a perfect avenue for everything else along with that. A blockchain is specifically designed for situations you have no trust in anything (except that 51% of mining power is not colluding in a specific way) - the rest of the time, there are much cheaper and simpler solutions.
The blockchain solves the problem of assignment and transference of property rights. Right now that process in many places is slow, expensive, error prone, and corruption prone. Blockchains completely eliminate that, full stop. Yes, you still need the authorities for enforcement, so obviously blockchains do not create some utopia where everything works perfectly, but they do solve big, real problems.
Notary services were for a long time independent of the State, they may still be in some countries and places. This is indeed something in which a global decentralized trusted ledger can help.