There are certainly many options to accomplish this. All of the solutions you linked are good, but I'd like to let you know that another option exists: Florin coin.
This coin enables embedding 140-character permanent messages into the blockchain, which are currently being used for a number of things, such as a color coin system (similar but not related to Colored Bitcoins) where users can create contracts that represent ownership of non-coin things.
This system would be perfect for what you're describing, and is being worked on at the moment. If you want, please send me a PM here or email me (support at colorcoin dot org) to discuss more. I'd be more than happy to help you reach your goal using the Florin blockchain. Our aim is to provide a solution that is easy for users to understand and deploy quickly, while retaining the fully decentralized and secure architecture of the blockchain.
You can view a live demo in my signature. Please be advised that there is no javascript in use on any of my sites, so no-script (and other similar addons that prevent tracking and annoying javascript vulnerabilities) will not reduce your experience whatsoever.
Thanks,
metacoin
THat is pretty interesting. I'll have to check that out. Is there only one message per coin? or can you continually chain messages into coins?