Here's an idea. Get a dictionary. (or any book for that matter). Instead of writing down the private key or code, you circle a few letters per page starting from somewhere in the middle, and skip a few pages.
Sort of steganography. I'm sure you can think of more ways to use every day things that will not attract airport security.
In-flight magazines that you're allowed to take home, tour book. A bunch of letters in a necklace. Handwritten with a sharpie on the inside of your undershirt.
Or my personal favorite, a microSD card hidden on or about your person, shoes, belt buckle, stitched to the hem of your pants or shirt sleeves, taped under your watch, or just stuck in your leather wallet (where you hold your credit cards, if you have those.)
A bunch of coins in a coin purse with one fake hollowed out coin; or two coins taped together with the card in the middle, should work just as well.
I think Elwar doesn't own a "home" so that's why he carries his valuables with him on his travels.
The idea of the microSD with an encrypted (with a simpler password than a full seed) file with the private keys is very good. You can even carry it in one of these:
http://the-gadgeteer.com/2009/09/19/hide-a-microsd-card-inside-a-nickle-spy-coins/Or hid it inside any other valuables.
If I were Elwar I would have already bought some cheap real state somewhere even if just to store my stuff. There are many places in first world countries where you can buy one for just a few tens of thousands.
Also, memorizing the seed is not that bad IF YOU HAVE BACKUPS somewhere. You don't want to rely just on your brain when in case of failure is when you would most likely need the money.