If we were to use yeast, we could additionally include methylation. We don't have to stop there: we could encode information in histone acetylation states, transcription levels, etc. to increase this density even further. Granted, how practical would that be?

Using the regulation machinery might be an interesting way to decrypt messages, if it were sufficiently complex a signalling pathway...