You can use a paperwallet - go on blockchain which seems the easiest way to do.
Edit: How come blockchain isnt a good reliable source for cold storage? for paper wallets, I was actually considering this..
The reason for this is the same reason they'd likely recommend against Coinbase. A computer being connected to the Internet ONCE could mean it's already been infected. To have 100% safe cold storage you have to ensure the system the addresses are generated on have NEVER been online before (at least after being reformatted).