I am a consultant for a company and I write the code for their Salesforce system, so legally they own all the code.  Therefore, I cannot post the code in its entirety. I did get permission to post snippets which should be clear enough to show you how to use the trigger/asynchronous callout/RESTful webservice approach that I did.

Below is the trigger, this gets called each time an Opportunity is updated (after update).  The 'if' statement (o.TerritoryId == null) will make sure the webservice only gets called if the Territory isn't set yet.  The line that calls the RESTful webservice is highlighted in red.  TerritoryRulesUpdate is an Apex class that has a method 'updateAccount' that does and asynchronous callout to the RESTful webservice (written in C#, see below).  I will post snippets for the TerritoryRulesUpdate class and the 'updateAccount' method below.

Trigger

trigger TR_Trigger on Opportunity (after update) {
		for (Opportunity o: Trigger.new) {
		    if (o.TerritoryId== null) {
			// make the asynchronous web service callout
			TerritoryRulesUpdate.updateAccount(o.AccountId, o.ID, o.Opportunity_Number__c);
					
		    }
		}
}

TerritoryRulesUpdate Class

public virtual class TerritoryRulesUpdate {

    
    public TerritoryRulesUpdate() {}

    //  Code omitted, but all the initialization of the HTTPRequest and HTTPResponse classes are done
    //  above and setting up variables to hold the endpoint.  (The endpoint is the URL to call the 
    //  Webservice that was written in c#)

    @future (callout=true)
    public static void updateAccount(String ID, String OppID, String SFNo) {
 
        TerritoryRulesUpdate t = new TerritoryRulesUpdate();
     //   After the class is instantiated, we execute the RESTful webservice using Salesforce's
     //   HTTPClasses.  We process the response (HTTPResponse) from the webservice.
     //   something with the response if I receive a CalloutException.

     //   Below is the code that actually does the callout with t.execute(req).  All these
     //   variables (req, res) were initialized above, but I had to omit how they were initialized.

        try {
	        TerritoryRulesUpdate.res = t.execute(req); 
            resBody = t.getResponseBody(res, req);

        } catch(System.CalloutException e) {
        }
    }
 }

RESTful webservice written in C#

The code below is the main part of the webservice.  Before this method is called, you will need to have the webservice login to Salesforce and create the binding for the webservice.  There are many examples of how to login to Salesforce via .NET, but here is a link: Salesforce using API Example.  The main part of the code is setting up the AssignmentRuleHeader and then updating the Account. We setup a field called 'Run Rules' that we set to true, but the AssignmentRuleHeader is what forces the territory Rules to update.  This is explained in the following link: AssignmentRuleHeader.  After that, all you have to do is send the update to the account back upto Salesforce.

       private void updateAcct(String AcctId)
        {
            ArrayList arrAccts_t = new ArrayList();

            //The results will be placed in qr
            RunTerritoryRules.sforce.QueryResult qr = null;
            /*We are going to increase our return batch size to 250 items
            Setting is a recommendation only, different batch sizes may
            be returned depending on data, to keep performance optimized.
            */
            binding.QueryOptionsValue = new RunTerritoryRules.sforce.QueryOptions();
            binding.QueryOptionsValue.batchSize = 250;
            binding.QueryOptionsValue.batchSizeSpecified = true;

            String qry = "Select Id, Name, Run_Rules__c FROM Account where Id='" + AcctId + "' ";

            try
            {
                qr = binding.query(qry);
                bool done = false;
 
                if (qr.size > 0)
                {
                    // Create the assignment rule header and add it to the proxy binding
                    AssignmentRuleHeader arh = new AssignmentRuleHeader();
                    arh.useDefaultRule = true;
                    binding.AssignmentRuleHeaderValue = arh;

                 }

                    while (!done)
                    {
                        for (int i = 0; i < qr.records.Length; i++)
                        {
                            RunTerritoryRules.sforce.Account acct = (RunTerritoryRules.sforce.Account)qr.records[i];
                            acct.Run_Rules__c = true;
                            acct.Run_Rules__cSpecified = true;
                            arrAccts_t.Add(acct);
                            recCount++;
                        }
                        if (qr.done)
                        {
                            done = true;
                        }
                        else
                        {
                            qr = binding.queryMore(qr.queryLocator);
                        }
                    }
                }

Jeff Douglas wrote an article that assisted me.  It shows how to call a RESTful Web Service as a callout in Salesforce.  The link is: RESTful Web Service Callout using POST with Salesforce.com. I also got some good information from this link on Salesforce's documentation on the HTTPResponse Class.  Finally, when it comes to testing the class and trigger, this Salesforce documentation gave me the best approach: Apex Code Test Methods. 

Hopefully, this gets you to a solution for your problem.  Sorry I couldn't give the complete code, but I think I addressed all the main areas of the code.  This is definitely not the only solution, but it is the one that works for us and has been implemented for a bout a year and has worked just fine.  Regarding the asynchronous callout, it happens immediately since only one Account record is being updated at a time.