The Tor user may pay the fee from a bitcoin exchange account. As far as I'm aware, exchanges do not offer their customers the option of signing messages.
The average fee users pay is below most exchanges minimum withdrawal allowed. Any users who couldn't sign messages from an address could be given an option to associate another address with their account.
if the Tor user's non-exchange wallet has many inputs to many addresses, and pays the fee from that wallet, which address(es) would the Tor user then have to use to sign the message?
Signing from any of those addresses should be OK.
not every wallet has the ability to sign messages, mobile and web wallets being the most obvious examples.
They can export the private key from their mobile or web wallet, then import it into a wallet capable of signing messages. The blockchain.info web wallet allows exporting private keys.