I hate to say it but there's a big problem with this idea as a result of the fact that we're talking about A. a paid store or B. Open Source code.

I'm not sure how you could make it and be sure in any way that the ad code wont just be removed and the application redistributed sans ads. Otherwise the option is to just put a price on it.