It isn't the GWT Same Origin Policy - it is the browser itself! The browser won't normally allow any XHR call to go out to a server that isn't the same server the page was loaded from.
The link you mentioned lets your server act as a proxy - thats one way to let the client talk to another server. The steps they take (create a servlet that forwards requests, configure it to point at the other server you want to use) do not require changes to the client.
Another option is to use the Cross Origin Resource Sharing - a way for the server to specify that the browser is allowed to contact it, even across domains. The catch: not all browsers support it.