I thought some more about it and I think the issue is that the value proposition of your product is not strong enough to get traction. One of the ways you can improve it is by converting it into a monetization channel for app developers.

So say a free game app has a 100K users playing the game and you know the location ( enable GPS in your SDK) of these users and the times when they are active (start tracking that too) etc then those users could answer a quick survey for larger brands (who pay per survey completed). So the survey is not about the game users are playing, but about a new movie that is launched or a new Xbox Game title that is launched etc. The free app could continue to be freely used if the user answers 1 survey every 20 times he or she plays the game. Survey can even allow you to show a relevant targeted ad next time or promote some other app game too.