Short Answer:
var s:ClassThatExtendsWebServiceWrapper = new ClassThatExtendsWebServiceWrapper;
s.serviceControl.endpointURI = 'http://service.com/service.asmx';
Long Answer:
Well I finally found a solution. Adobe seems to have made this much harder than it should have been.
Web Service classes that are generated by Flash Builder 4 extend the com.adobe.fiber.services.wrapper.WebServiceWrapper. WebServiceWrapper has a property called serviceControl that can be used to control the service. The problem is that not all the members of serviceControl are accessible at the application code level. Lets assume that I have a web service called GameService. When I use the data tool to connect to the web service by providing a WSDL, Flash Builder will create two classes for me automcatically.
internal class _Super_GameService extends
com.adobe.fiber.services.wrapper.WebServiceWrapper
{ ... }
public class GameService extends _Super_GameService
{}
_Super_GameService contains all the automatically generated code to make calls to the web service. GameService contains no code itself, but unlike _Super_GameService, it is public. The idea here is that any enhancements that we need to make can be made to GameService, then later on if we need to update, _Super_GameService can be regenerated, but out changes to GameService will not be overwritten by the code generation tool.
Now this leads us to usage of these generated classes. Typically all I should have to do is create an instance of GameService and call a method on it. In this example DoSomethingAwesome is a method available on the web service.
var gs:GameService = new GameService();
var token:AsyncToken = gs.DoSomethingAwesome();
Now this will call the service using the URI of the service specified in the WSDL file. In my situation I wanted GameService to connect to a different URI. This should have been simple, but things fell apart.
My first problem was that viewing the documentation on WebServiceWrapper (http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/com/adobe/fiber/services/wrapper/WebServiceWrapper.html) did not render properly in Firefox. So when I was reading the documentation I wasn't getting the full picture. This really needs to be fixed by Adobe.
Viewing the documentation in another browser helped me find out about the serviceControl property of WebServiceWrapper. serviceControl is declared as a mx.rpc.soap.AbstractWebService. AbstractWebService does have an endpointURI property which makes the following code valid.
var gs:GameService = new GameService();
gs.serviceControl.endpointURI = 'http://game1.service.com/GameService.asmx';
The other problem I had is that for some reason the endpointURI property of serviceControl does not appear in the Intellisense context menu. So since I didn't see serviceControl in the online documentation at first, and I didn't see endpointURI in intellisense, I didn't realize the property was there to be set.
If you look at the source for AbstractWebserivce, (http://opensource.adobe.com/svn/opensource/flex/sdk/trunk/frameworks/projects/rpc/src/mx/rpc/soap/AbstractWebService.as) there doesn't seem to be an Exclude tag to explain why endpointURI does not appear in the Intellisense context menu. So I don't know what is going on there.