Do you already know what the change address in question is?

If so, you can just paste your change address into the Sign Message dialog box and it will work.

I can see how signing with a change address could be an issue, as they aren't listed in the Address Book dialog, but as long as you have a convenient way to find your change address in question (like copying from Blockchain.info) just pasting it in should work.