Make a ring engraved with a private key forged in the fires of Mount Doom in Mordor
The Key only becomes visible when the ring is heated in fire
I think Charlie Shrem did this already......
How about storing them in plane sight??? Make a bunch of new addresses in a wallet each with 1 satoshi. Then pay all those satoshis back to one of your primary well-known wallet address that you can recognize. Use the 2nd number/letter of each address as the passphrase for a brain wallet which then give you a private key/public key. HIDDEN IN PLAIN SITE and won't go away unless bitcoin is dead.
--Now that this method is said it is not safe (and not really random either), DO NOT ACTUALLY DO THIS!!! lolYou could possibly do some variation of this. Instead of the second number, you could use the last digit or the second to last digit. You obviously would not use 1 satoshi inputs, but instead use inputs starting at .01
BTC and increasing up to 1.12
BTC in .01
BTC increments, and having the digit that you use for the .01 input as the first number/letter of your passphrase, the .02 input the second digit and so on until the 1.12 digit is the last digit of your passphrase. You could first create transactions to an intermediary address (or several so you would need to go back a few 'hops' to get back to your passphraise inputs), then create the brainwallet and fund the brainwallet.