Firstly Hello,
As far as I've heard or seen, two versions of the same app (Free and Pro) should be two distinct projects. You could, but should NOT, use the same app and just check for a flag saved in the Prefs, but root users can override that (as you already stated).
You could also use Google's in App purchase to verify this as the other answer states. In my opinion you should not use the same project and check for a flag because it's bound to create some overhead, especially if you check using the Internet. If the user has a slow or unreliable network connection his experience will suffer.
The "clean" way to do it is to make two distinct apps like everyone else does: users can install the free app, or the pro app. This is ideal because you have two distinct options for users and if they want the pro version they don't need to get the free one and then see the option unlock in the menu. It's just way more straightforward for users.
I recommend you build the pro app first and after it is completed derive the free version by restricting functionality and including adds because it's easier to strip it down than to add-in. After you finish the pro version, just click on:
File -> New -> Project (pop up menu appears) -> select Android folder -> select "Android Project from Existing Code" -> select your App and click Finish
The drawback is that if you spot a bug you must fix it in both projects. If you want to optimize finding bugs, you could build the free version, put it on the market and fix the bugs reported by the end-users as well as the ones you spot. After you consider everything to be fine, you can create the pro version from the existing code and carry on with that.
ps: I realize I filled this whole page, but this is my first answer here and it seems I'm overenthusiastic :-)