You can get an offline paper wallet generator from here:
https://github.com/cantonbecker/bitcoinpaperwalletI would personally download that to USB stick or some other storage method, then i would boot onto to example Ubuntu live cd that does not have an internet connection and generate the wallet from there.
Do not connect to internet at all while generating the wallet. Then print the paper wallet via printer (still offline, you can have a local connection to the printer tho.)
That should do the trickt, let me know if you need more help with this