That's a very technical viewpoint. The API agreement tells not to share the key, which obviously does not mean you can't include it in the app binary. I interpret that as not being allowed to publish the key with the source code though.
That's pretty weird and questionable interpretation, since if I have a binary — I have the key, even if in some obfuscated form (even that isn't usually true with APKs though), but whatever, if it works for you — fine, then I have a solution to your problem.
Don't include API_KEY in the published source, include rot13(API_KEY).
You have to consider the intention of the service provider, which in this case is more geared towards mobile clients than web services. It's perfectly clear that binaries will include the API key, no interpretation needed on that part.
It's the source code part that is open to interpretation. I could of course just ask for explicit permission for that.
