Hex is suitable.
Get the arithmetic right, and you get the encoding right.
Just don't use base64.
Base64 is a big-endian file encoding scheme that takes the data to be encoded and splits it up into groups of 24 bits (3 words of 8 bits). If there's any slop, base64 encoding pads it on the little end. Emphatically not what you want.
This is basically nonsense. If you use it right then just like base58 and hex, base64 is a perfectly valid way to encode any
bytes at all, including a private key represented in the usual way. The padding on the end ensures that you can decode the exact same bytes that you encoded despite the grouping. That said, its character set is a superset of base58's (+/O0Il are the extra chars), and since he doesn't "have the means to use all the base58 charset", base64 will be an even worse option. And maybe if you wanted to encode the private key as a number, without specifying how that's turned into bytes, things could go awry? But really, [some bytes in] == [same bytes out].
I'd recommend the casascius or brainwallet options that luv2drnkbr linked to (I haven't used pybitcointools, but I'd expect that's a good option, too). Be sure to test encoding/decoding/decrypting before you move any real money to something like this.