Bitcoin headers are probably never going to be changed much, so you can try encoding messages there. You only have limited space in Merkle Root (with partial hashing collisions) and Nonce, so you won't be able to encode much there. You could try encoding something in the hash of the block, but that would make it very expensive (storing n bits would mean creating about 2^n blocks before a message would be encoded).
If you believe the coin generation transactions would not be pruned, you could try using them for encoding your messages, which would be quite cheap if you mine your own blocks, or have someone that would let you encode some messages in their blocks.
After that, there aren't that many places that could be safe from potential pruning. Then again, some people will probably be keeping the entire block chain, so message encoding in the traditional way might not ever go away...