Bitcoinpaperwallet.com. Print one and have fun.
If I go that route, I'd need to buy a fireproof safe/lockbox.
Actually I'd probably encrypt the PDF and store it somewhere local as well.
Someone mentioned making an image of the private key, and encrypting that. That sounds pretty slick to me, and extremely difficult, if not impossible, for any virus to steal.
This is one of the routes I will probably take.