In my personal opinion make a paper wallet and back those paper wallets up with copies. Laminate all of these paper wallets and store the second and maybe third copies at separate locations.
OP, screw what anyone else told you... ^^^^^ THIS is all you need!
Go use Vanitygen, get yourself some addresses and pub/priv keys, print it in triplicate, laminate and store in locked, secured places.
By using Vanitygen, you get addresses and keys without ever having to use a third party or sync a Bitcoin client, and you can even attempt to get an address with a custom starting word or name!