Is it possible to put these assets onto the blockchain so they can be traded without the participation of the issuing government agency? If so, how would that occur? The biggest challenge seems like it would be the gatekeeping since the taxing authority will not do anything with the blockchain so a trusted third party would have to do some gatekeeping — at least initially.
It is possible to do this. As mentioned, the issues you face would be legal, rather than technical.
The technical implementation would likely consist of a series of smart contracts that live on the network and contain all relevant details of the lein. Depending on how it is structured, it would likely be held in a registry with other leins.
Each member of the transaction(s) would need to have their addresses live on the contract. So the government agency who would be paid must have an Ethereum account, provided they accept ETH.
Again, technically this is not a difficult task. Legal and infrastructure are where this plan becomes difficult.