If I were you, I would rent a server (possibly amazon) and create a database and insert our api key with a simple encrypted string (hash, etc.).
ID - Name - androidKey - key
1 - GoogleAPI - AJKBSASHUA9 - yourAPIKey
2 - YandexAPI - 5A6S5D6A53C - yourAPIKey
.
.
.
Then you can create a service that starts with your name android packageName;
http://example.com/API/getAPIKey/
?packageName="yourPackageName"
&androidKey="AJKBSASHUA9"
POST, .