download the webpage
https://www.bitaddress.org/take your computer offline ( remove the internet wire )
load a linux live boot cd/usb.
print out a public/private key pair using that bitaddress webpage.
you've got yourself cold storage.
I will definitely go for this way, just in case I want to store a lot of bitcoins, so I think a paper wallet is the safest but have some disadvantages like paper degrade or the paper itself can be lost all together.