A cumbersome but reliable way of doing this would be to make your application use a proxy server, and then write a proxy server which makes the changes you need. The proxy server could be in-process in your application; it wouldn't need to be a separate program.
To use a proxy, set a couple of system properties - http.proxyHost and http.proxyPort. Requests made via HttpURLConnection will then use that proxy (unless they specifically override the default proxy settings). Requests made using some other method like Apache HttpClient will not, i think, be affected, but hopefully, all your requests are using HttpURLConnection.
To implement the proxy, if you're using a Sun JRE, then you should probably use the built-in HTTP server; set up a single handler mapped to the path "/", and this will pick up all requests being sent by your app, and can then determine the right URL to send them to, and make a connection to that URL (with all the right headers too). To make the connection, use URL.openConnection(Proxy.NO_PROXY) to avoid making a request to the proxy and so getting caught in an infinite loop. You'll then need to pump input and output between the two sockets.
The only other way i can think of to do this would be to override HttpURLConnection with a new handler which steers requests to your desired destination; you'd need to find a way to persuade the URL class to use your handler instead of the default one. I don't know how you'd do that in a clean way.