How about having incomplete private keys in the wallet?

Every time you make a transfer using a certain key you would need to add missing characters using a printout that you make when the wallet is created. The program would then also transfer any difference in BTC to a new private key so that effectively each private key is only used once. You could also store the "printout" in some file of your own choosing in case you lose the printout.