Yeah, BTW the good thing about these stores is that they install apps normally, by launching the system APK install dialog, instead of the rootkit-style thing Google Play does.
It uses special privileges to run the installation in the background. Google Play Services is frequently called a "rootkit" because of stuff like that.
You can build the app, and to make it functional you could request your own API key, so I think it satisfies the label. Requesting API keys as a regular end user isn't anywhere near being realistic though, so that's not an option for distribution.
From pawadu's response above it sounds like your app would satisfy the requirements if you have a build parameter or similar that lets them specify the key.
There's another discussion thread [1] which takes a strict stance more explicitly: "I don’t see how something that contains a ‘secret’ key [...] can be Free Software. So we just don’t publish such applications."
Other alternative app stores are the Yandex Store (https://store.yandex.com/) or the Amazon App Store, those include non-free software too.