Instrument an Android APK

How to instrument an Android APK when the source code is not available?

I'm building a testing tool that uses an APK as input and I need to instrument the APK. Basically, I want to instrument all the occurrence of a specific function (e.g. foo) and change the values of the arguments. For example, if the APK uses the function:

foo("x")

The instrumentation has to change the argument

foo(9)