The new Android License Server should help a bit. You embed your public key inside the app and it checks against your private key on the License Server in runtime. If someone merely changes the resources to claim an app as his own, the users running the app would still check against your private key and failed as non-paying users. Of course if the code containing the public key is reverse-engineered and replaced with a new public key, you are still screwed. Obfuscation would help in that case.
Yes, this is possible, and was among one of our "solution list" (not necessarily checking against google's server, but could be our own server), but it's not much harder (if harder at all) to take out the authentication code than just change a string name in the app...
One way to raise the bar is to download critical pieces of code from a trusted code server in runtime. The client code authenticates first with the License Server using its public key and gets back an authorization token, which expires with time. It submits the token to download the code from the code server, which checks the token against the License Server.
To raise the bar even higher, make the downloadable code expirable or embedding the public key to re-authenticate once downloaded.
Of course a persistent cracker can still run a sniffer to capture the runtime code, reverse engineering it, remove all the checks and stitch the code back together. It just makes it harder.
The new Android License Server should help a bit. You embed your public key inside the app and it checks against your private key on the License Server in runtime. If someone merely changes the resources to claim an app as his own, the users running the app would still check against your private key and failed as non-paying users. Of course if the code containing the public key is reverse-engineered and replaced with a new public key, you are still screwed. Obfuscation would help in that case.