I created this answer which I think pretty accurately describes the process you would need to decode the blockchain.
I dislike the word blockchain when used for Ethereum because it can give people the wrong impression of how Ethereum works. In Bitcoin and a lot of crypto currencies, they use blocks to store all the information that has changed that is trying to be added to the chain of information. If approved, everyone slaps the block on the end of the chain and now knows that to be the last valid transactions on the chain.
Ethereum adds state to a blockchain which requires not just UTXO's to be accounted for, but every account on the EVM has to be readily available in case someone calls a smart contract and wants there to be a state change. They handle this by creating merkle patricia trees that store new changes and also reference the entire previous EVM so that it too can be referenced in calls. I could explain more about merkle patricia trees, and if that is required please comment, but I don't think it is necessary for your question.
I just wanted to clear up that understanding so we both can be on a similar page about how Ethereum handles blocks. I don't think you want to change the structure of how data is stored in Ethereum, but instead change what get's accepted to be added as data to your implementation of Ethereum.
So you want to create your own private Ethereum implementation that adds a prefix to each block. That sounds like a requirement that you want to implement, not at the EVM level, but instead as a requirement when mining.
If you look at this block. You will see that it has extra information in ASCII that says: "ethermine-eu5". I am assuming you want to enforce that to instead say, "Block mined ethermine-eu5". You could either handle this from the nodes or from your mining client. Geth is one of the more common implementations of Ethereum and they could say that if a block comes in without "Block mined" as a prefix then it will decline the block. But if another client decides to accept that prefix such as parity then there would be a split in how to handle that change.
I don't know how you are currently creating your own private chain, but I believe that you should change the code of the client to enforce every block that is accepted to have a prefix in the Extra field. If another node chooses to do something else then they would be removing themselves from your implementation of your blockchain.