The safest, easiest, and most effective cold storage is very simple: bitaddress.org
Wanna be extra safe, download their source files (link is on the home page) to a USB and run the webpage on a laptop that's never been online. Bip38 option. Pick a passphrase. Generate. Print (or write it down, but be careful). Bank Safe Deposit Box. Done.
-B-
Buy a Trezor. Write the seed down and store via Bitt's advice above.
Your best bet is to somehow generate a private key on a computer that has never been connected to the internet nor will be connected to the internet until the funds from the private key it generates has been transferred to another address
Thanks, for added security would it be at all any value to get a hardware RNG to help with such a task, or the fact it being an offline computer good enough security?