One thing to try to appease Google Play is to change the app, so it's a set of instructions/downloads as follows:
* If Unknown Sources isn't ticked on, the first screen tells the user to go to Setttings/Security and tick on Unknown Sources (maybe that screen could be loaded by the app to make it even easier?).
* Next, the app downloads the apk from the CM site and installs it.
* Ask the user to uncheck Unknown Sources if they had to check it on in the first step.
* Run the downloaded app (exiting the original app at the same time if possible).
Would *this* violate any terms of service of Google Play (written down or otherwise)?