So why not shorten your password to 63? Will one character really make that much difference if someone is determined to crack your password? And why are you limited to hex digits? Why not use other symbols and characters as well?
A 256-bit pre-shared key is used in WPA authentication. If you type a password, this key is calculated by applying the PBKDF2 key derivation function to the passphrase, using the SSID as the salt and 4096 iterations of HMAC-SHA1. In my case, I am entering the raw PSK manually, so I can't say for sure that some passphrase exists that map to my PSK. Hex digits make it easier to enter this 256-bit binary value and it is a standard way to enter raw PSKs.
Have you considered use of WPA2 Enterprise? EAP-TLS can totally eliminate PSK and all of its problems without extreme approaches.