Actually there is no way to do this without touching the Internet. Even if you decide to dedicate an entire computer as your offline wallet PC you will still need to connect to download the OS and bitcoin wallet/client software. If you are using Linux on your "offline" PC you will need to connect regularly to update software or end up in dependency hell.
Just to be pedantic here, I can think of one way that is completely firewalled. You build your own computer using old-skool pre-internet technology (or just dig out that old ZX-Spectrum from the attic) to be sure there are no NSA infected parts inside, code up your own address generator from scratch (I take it you're allowed to refer to the online wallet code and algorithm documentation, perhaps print it out at your local library), make a nice hot cup of tea (it will make a good source of entropy for your hardware RNG), then Bob's your maiden aunt.
