There are several alternative clients available. Like unique_id in his answer, my first recommendation would be AppBrain App Market.
But speaking about Android without Google, this probably won’t work at all: AppBrain depends on the Google Play Store app when it comes to download the *.apk and install the app.
As I’ve pointed out in my article series on this topic (linked above), this is where the NOGAPPS project comes into play. It offers e.g. the BlankStore app, which is a “naked” variant of the Google Playstore App – stripped down to the essentials: You can search the Playstore, you can install free apps and those you already have bought (you cannot, however, use it to buy apps – that you’d have to do e.g. via the Web frontent of the store itself), and you can check for updates to apps you have installed (actively; there are no update notifications).
In addition to that, I’d recommend to install StripSearch – which offers additional features when searching for apps: you can tell it what permissions the searched app should not have, and it limits the result set accordingly:
StripSearch (source: Google Play; click images for larger variants)
And not only that, as the screenshots show: you can modify filter presets and create your own, you also can set a price limit, and more.
That’s the combination I use on my “Google-free devices”, and it works perfectly: license validation for payed apps included (via BlankStore that is), installing/updating apps, all that. Additionally I’m using F-Droid, and download *.apk files from the safe “Apps” repository on Aptoide (see How safe is it to use Aptoide? on our sister-site Android.SE). Only thing I miss on those devices is Google Cloud Messaging – as without that the Stack Exchange app doesn’t notify me of events like new answers to my questions, or a comment addressed to me. For accessing the Google Play Store without using any of the GApps, to my knowledge there is no better combination. Though, as you’ve already figured, you could also use AppBrain as front-end: I’ve not tested this, but I guess it would then use BlankStore for installs/updates – as BlankStore poses to be PlayStore (all NOGAPPS apps emulate the Google APIs, so this should work).
