How can I use message signing to prove that I have private keys for many different accounts?
You can sign a message or export the private key of all the addresses in your wallet, including change addresses.

If you want to have a single message signed by all your keys the only solution I see would be to sign a message with the first key, then sign the signed message with a second key, ad nauseam.

Strictly from an encryption point of view I don't believe it is possible with ECDSA to sign with multiple keys in the same signature, I might be wrong here though.

As you may already have guessed, the most practical solution would probably be to consolidate your funds into a single address and sign a message with its private key. But it has a privacy tradeoff.