Is it possible to make a paper wallet without a computer?
Practically speaking, no. Possible, yes:
http://bitcoin.stackexchange.com/questions/7491/how-to-generate-keypair-completely-offlineHowever, an intermediate option is to use dice or playing cards to generate your own random numbers so that you're only using the computer to do your hashing/encrypting.
In fact, I just implemented this feature on
https://bitcoinpaperwallet.com