There are plenty of ways to accomplish that, the easiest of which that works today would be to stuff data into unused public keys of an OP_CHECKMULTISIG transaction.
In case it helps other readers of the thread... If I am understanding correctly:
1) the idea here is that you can use something that looks like a public key, but which you don't actually have a private key that hashes right for it, since you don't need that particular private key to spend as long as you have private keys for other addresses.
2) any 64 bytes of entropy can be used as a public key, as long as you don't need the private key
Please correct me if I'm wrong.
https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addressesI'm still fuzzy on how this could actually be implemented.
How many public keys are currently usable for m of n signatures? Are OP_CHECKMULTISIG transactions "official" and generally relayed by miners, or are these still in a grey area? I did google a bit, but I couldn't figure out where to look to determine what transactions can generally expect to be supported. Obviously it's important to have a good grasp on this for people steering mastercoin.