I think that customization of TaxClassInfoProvider.GetTaxesInternal(ShoppingCartItemInfo item) I've mentioned above should work for you. It returns list of taxes for given item. You can contact your web service, get tax for NJ, create empty list of IItemTax with one ItemTax object representing tax obtained from web service.
Code example for illustration (null-checks and error handling missing):
var address = item.ShoppingCart.ShoppingCartBillingAddress; // Or ShoppingCartShippingAddress
var taxValue = GetTaxFromWebService(address.AddressCity, address.AddressZip, ...);
var result = new List<IItemTax>
ItemTaxID = "0",
ItemTaxDisplayName = "My Tax",
ItemTaxValue = taxValue,
Also, some kind of caching should be considered not to contact web service too often - have a look at CacheHelper class.