Using the free version + paid unlocker approach (http://www.marvinlabs.com/2011/01/sharing-code-full-lite-ver...), you can gift the paid version by sending just the unlocker APK to the user. Since all the functionality is in the free version from the market, they'll get updates normally. That said, this is really cool - I was thinking of building something like it for my applications.
Currently you can't control the number of times a coupon has been used, but you can control its lifetime.
If you get a new phone (and the coupon it's still valid) it will work, otherwise it won't.
We are working on a SaaS that solves exactly this problem combined with some additional things except you don t have to enter any coupons, its completely managed by the back end.
If you're into that sort of thing take a look at how I handle SaaS billing in my GeeTasksLite iPhone app. Try to cheat your way around, too. :) If you need to get in touch with me, just contact GeeTasks support.
The Apple's Appstore has coupons for free installation (up to 50 coupons per release).
I have also designed my own billing system, which has server-backed "free trial", time-limited purchases, and of course "we want to thank you this much" free orders. You can see it in action in my GeeTasksLite iPhone app. I'm thinking about selling this billing system as a library and a service (the server side).