I had the same problem, what I settled on is making two android apps, one called my_epic_app_free, and the other my_epic_app_paid. What I would do is only make changes to the paid version, then I have a separate java console program, all it does is access all the .java files directly from disk, copy them into memory, fiddle with the package names and manifest lines, then paste them directly into the free app. I have this on a button push on the desktop so when I'm done developing on the paid version, I press the button, then compile the free version. I have both the paid app and free app communicate to eachother, the user can even install both of them, and the free version sees the paid, and unlocks to the paid version.
Another idea is to make the paid app just a bare bone program which contains a keyfile. The paid app, if run, will automatically run the free version, and the free version will behave as the paid version.
The free app checks the presence of the paid app's key file, and if it exists, then it would unlock the free app. This prevents code duplication. The package names still have to be different but ideally the paid app would not need to be changed often.
Benefit: No user data/settings are lost when "upgrading" to the paid version.
Drawback: If the user installs the paid version first, they will have to be directed to install the free version which is a hassle, why do they have to install two apps for the paid version?