How can I use a custom prefix for international calls?
The only apps I have found to be able to do this kind of editing are SIP dialers like CSipSimple and SipDroid. They integrate into the regular call setup and can run a set of rewrite rules and filters to decide where and how to place the call.

I believe both can do this even for regular (cell) calls, and even when no SIP provider has been configured.