I hastily threw together a version of #Conversations_im that has no address book integration and doesn’t ask for Contacts permission.
This seems to have made it through Google Play review just now meaning the app is now available on Google Play again.

No indication from Google that they were in the wrong and hallucinated the whole "uploads contact list" thing. Instead I had to walk the path of least resistance and remove the useful and entirely harmless feature of address book integration.