Case in point: valid user credentials and it doesn’t matter what app is trying to authenticate. Issue a different key for every user (or every user per login or device) and your problem is solved.
Even if your app doesn’t require any login there’s no reason you shouldn’t go through the same process. Every device gets its own key and then you apply limits to it...
OK, this depends on what you mean by an API key. If you are referring to a security token that identifies the user, then yes, you should always be creating a new key per user, and often per session.
However the term API key may also refer to an App key, intended to identify all users of a given app. The intention there is to be able to engage and widespread revocation or throttling in case an app is misbehaving or compromised. You cannot keep this sort of API key secret because it must be shared and must be available.
In the non-user device scenario you mentioned, I’m pretty sure you would actually be better off simply having the device generate a random GUID instead of going through a pointless negotiation to hand out a random GUID.
I was actually referring to both, and I think the same process applies. Even if the API key is not for your service (like, say, a Google Maps key) there isn't any reason you can't fetch that dynamically from your server. There are also various solutions for secret storage on every platform (iOS and Android at least) that you could use to store it, rather than it being "public" in the app package.
Even if your app doesn’t require any login there’s no reason you shouldn’t go through the same process. Every device gets its own key and then you apply limits to it...