Admittedly, this proposal comes at the cost of a bit of convenience. I understand that... I also want to say that I did some searching to see if anyone has documented this process before but I couldn't find much.
Brain wallets are tricky to get right, as we've seen in the past with practically a new story every week of how someone lost their brain wallet coins. After thinking today that I really wanted to move my coins to a brain wallet and also concluding that I just didn't want to have to remember yet another long password, I came up with the idea to combine the use of multi-signature transactions and pay-to-script-hash outputs.
The idea is simple. You send your coins to a 2-of-3 multi-signature output. One of the keys will be generated as before with your brain wallet software. Another one of the keys will be generated for you using bitcoin software (you can use brainwallet.org's random key generator, for example) and you save it in a text file encrypted with strong GPG. The third key can be generated from anything else you wish, but ideally you give this third key away to your spouse, store it in a bank safe, store in the cloud, or wherever.
So this 2-of-3 transaction output is really defined only by the output script. This script can be hashed and turned into something that looks just like a bitcoin address except the address starts with a `3...'. You can then send your coins to this address like you would any other address. These are called Pay-to-script-hash transactions (P2SH). But of course, most of you know this already.
The benefits for the P2SH output is that an attacker trying to steal your coins doesn't know how many keys there are or how many keys are required to spend the output, nor the order of the keys required to produce the proper transaction. In fact, he doesn't even know if it's a multi-signature transaction at all.
Here's an example of how I might use this system:
1. I generate key1 using offline brainwallet.org software by hitting the 'random' button a few times and copying the "Private Key" (starts with a 5...) to a text file, encrypting it with my GPG key and storing it on my local machine and a remote backup. I may even print it and store it in a safe, like you would with a paper wallet.
2. I then come up with a strong brain wallet passphrase and enter it into the passphrase box. This produces key2 (it is never written down or saved, like a normal brain wallet).
3. (Don't use this step if you want to use 2-of-2 multisignature transactions) I ask my wife to type in a semi-strong password into the passphrase box. This produces key3. This key is never written down, as it is a brain wallet only in her head. I don't know it.
Using the public keys for each of the 3 private keys generated above, I produce a 2 of 3 multi-signature transaction. The output script is then hashed, and a P2SH address is generated from that. Coins are sent to the corresponding address.
Normally, if I need to spend these coins I know how to access key1 and key2 and can produce the necessary signatures. Use of the third key should be rare and only for emergencies. An attacker doesn't know how many keys there are nor how many are required. In the event that I lose all hard copies of key1 or I forget my brain wallet passphrase for key2, I can ask my wife for access to the third key. You never need to store the output script, either, because you can always reconstruct it as long as you know the public keys.
This strategy should provide the same security as a brain wallet, yet also eliminate any possibility of brain wallet scrapers from ever stealing your coins. A nice benefit is that your brain wallet passphrase doesn't have to be as strong. Should a scraper ever figure out your passphrase, they would never know it because the Bitcoin address associated with your brain wallet never had coins sent to it (only the hash of the multi-signature script is public) and a scraper would pass right over it. This doesn't mean you can pick weak passphrases, because if either of your other keys were compromised then a weak brain wallet is a liability.
So that's it. Here are a few more extension ideas:
1. use 2-of-4 multi-signature, and have the fourth key be generated by your mother or someone else close to you. This way, if anything happens to you, they can access to your coins. You'd need to pick two people for keys 3 and 4 that you trust would never conspire against you, of course... (I think this may be a problem if only n-of-3 transactions are standard right now)
2. decoy coins. Take each of your keys and send a small, but modest amount of bitcoins to them (say, 0.5 or 1) and add those addresses as 'watch-only' to your Bitcoin software. If your hard copy of key1 is ever compromised and an attacker moves those coins you can be alerted immediately, indicating that you need to move all of your other multi-signature P2SH transactions to new ones.
OK, tear me up! If this gets enough positive feedback, I'd be happy write up some python scripts to generate and spend transactions like these.
Implementation (BETA, Use At Your Own Risk!!):
