Here's what I do for cold storage, this method has proven secure for me for over 1 year (no lost coins)
1. download the latest copy of Tails (
https://tails.boum.org/) and burn a live DVD
2. boot computer from Tails
3. go to
https://bitaddress.org, load page
4. disable internet connection
5. generate paper wallets (I recommend using BIP38 encryption - just make sure you will always REMEMBER THE PASSWORD)
6. print
7. shutdown computer
And there you have it, fresh private keys that exist nowhere else but the piece of paper in front of you.