I think the safest and most paranoid idea I've head so far is to physically print your private keys. I am even tempted to print them on a freaking gold plate!
That's awesome, "My Bitcoin is backed by gold! Have at that you fiat based currency!"
Technically there is no reason why bitcoins (realistically only a portion of them) can't be backed by gold, but that would kill the whole decentralized thing bitcoin has going for itself.