How it currently CAN be done
During my morning routine reading my RSS feeds, I stumbled on a review at N-Droid, discussing an app named APEFS. This app is developed by German students (hence its description on the Playstore is in German, even if you set the language to English). But for our non-German readers, a short description here:
Basically, APEFS is an alternative front-end to the Google Playstore. You browse the playstore as you do with the original app, and search it the same. But when on the results list1, an advanced filter2 comes into play:
As the second screenshot shows, you can select what permissions your wanted app is permitted to have (checkbox marked), and what permission it should not have (checkbox unchecked).
However: While this can be used to filter out apps with unwanted permissions (e.g. show only apps whitout the Internet permission), you can not restrict your results to the opposite (e.g. show only apps with Internet permission). The app clearly targets at users concerned about their privacy/security -- and according to the review (I just found it a couple of minutes ago, so I could not test it yet) it does a very good job.
EDIT:
As it's already a year ago, and the promise on the APEFS Homepage (GTransed to English, as their own English version doesn't have that statement in the first paragraph) seems not to be fulfilled anytime soon (the app is still offline): Please consider the web-based solution from my other answer as an alternative meanwhile.
