Better app discovery could help a lot: even if 90% of your potential customers are unwilling to spend more than $0.00 for apps, that still leaves literally millions who would consider buying if they were only able to find it.
It's not an easy thing to solve though, I think the promotion and discovery model should be changed fundamentally. First of all ratings and 'most popular' should be completely eliminated from the equation, because they are self-fullfilling and relatively easy to manipulate. I would like to see some form of syndication for apps, which suggests me apps that fit my preferences and use cases, which could (and likely is) vastly different from other people. For example, I would love to be able to find (by whatever means possible) more developer-oriented apps (either on desktop or mobile) for things I don't even know I could use. The current app store model provides basically zero opportunities for this, I can go to the 'developer section' in the app store and look at the top 25 apps but there my options to discover apps stops. There really is no way for niche apps that could find a decent number of paid customers to promote themselves.
Besides better app discovery, trial versions are really essential. I would like some kind of subscription service that lets me try literally every app I want, but only for one month after which I would have to buy it at the regular price.
Yet another idea could be to allow developers to join forces and bundle their apps, dividing the profits through some kind of agreed-on distribution. This way low-volume/high-margin apps that would be hard to sell in large numbers as standalone could piggyback on high-volume/low-margin apps.
Plenty of possible improvements.. At any rate I feel something needs to change, because the current situation is hurting creativity and decreasing the quality and value of many app categories.