Counterparty could solve this, on Bitcoin's blockchain [1]:
> Counterparty works by storing extra data in regular Bitcoin transactions, which makes every Counterparty transaction a Bitcoin transaction, albeit a very small one. When Counterparty transactions are broadcast to the Bitcoin network they are verified by Bitcoin miners and saved in the Bitcoin blockchain to make a secure, verifiable record.
> Counterparty works by storing extra data in regular Bitcoin transactions, which makes every Counterparty transaction a Bitcoin transaction, albeit a very small one. When Counterparty transactions are broadcast to the Bitcoin network they are verified by Bitcoin miners and saved in the Bitcoin blockchain to make a secure, verifiable record.
[1] http://counterparty.io/