This makes a strong case for simply never submitting apps to Google Play. It's easy enough to release them directly and explain to users how to disable Android's default security restrictions. If an app is of sufficient reputation and quality, this won't be a major stumbling block to obtaining installs.
