Since all the coins actually reside in the blockchain, and the wallets are basically just keys to access them, as long as you have those (public and private addresses), there are a few ways to make a paper wallet happen if it isn't too late.

They do take a little bit of work though.

If you have some graphics skills, you can print your own design, and place the public and private key to an address you generate and add coin to, for him somewhere on it.
You can go to the console and get the private key to an address.

You can also go to walletgenerator.net (I would do the download of the page and open it while offline to help with security).

The Guncoin block explorer can be used to see the information about the address once it is created.

Good luck, Great idea for a gift.