You need an air-gapped computer. An old (circa 2000 or so) laptop running some unix-like is probably best.

I'm involved in a project to produce a cheap hardware widget to make this kind of thing easier (http://cryptome.org/2013/10/bitcoin-usb-gpg.htm) but it is not yet in production.