I am so far surprised that no-one seems to be interested in this (for things such as Bitcoin100) and (if the feature actually does get added) will be creating a "project management" package for the CIYAM software platform that will integrate with bitcoind to work with such "non-anonymous" addresses.
If you don't want to patch anything, you can use a client like blockchain.info to handle the key. It will return change to the spending address.
If you want to never put the private keys on an online computer, Armory's watching wallets would be safe to distribute for auditing and the change addresses would be deterministic. It's probably best to use that bitcoind patch though.