I'm currently developing a mobile app (iOS based initially) that consumes multiple APIs. Currently we're storing API keys as strings in the the prefix header file, and initializing most of the APIs when the app loads. It's occurred to us that it is quite easy to extra the API keys from the executable on a rooted device. Furthermore, if one of our API keys gets compromised and we are forced to change it, we're handcuffing ourselves by hardcoding these values in the executable.
What is the most secure way to store these API keys, and furthermore what is the most secure way to distribute them over the air (ie using a remote configuration pattern)?