I haven't tried this practically, but I am sharing based on my understanding. Please feel free to comment if any thing is practically incorrect.
Approach-1:
Just configure the new domain with the old domain name. So only hosting location will change, the app will still have valid domain name to redirect.
Approach-2:
While registering the Provider Hosted App, we use following URL.
https://SiteURL/_layouts/15/appregnew.aspx
here we provide the App Domain
and Redirect URI
. And it gives us a ClientID
and ClientSecret
key which we use to configure our Provider Hosted App.
Now we have our ClientID
. Now lets say our domain has been changed, just go to the following URL
https://SiteURL/_layouts/15/appinv.aspx
You will get following form

Just enter you existing ClientID
and click on Lookup
. It will fetch already existing details.
Just enter the new Domain
and RedirectURI
here.
By doing this, the app will still have the existing ClientID
and domain also get updated.
Just upload the app again in Catalog and your customer will see update of the app after 24 hours, and after updating the app will run from new server.
(During Mean time keep the old server working so that functionality of your app continue working!!!)
Note: Again, I haven't verified anything practically, it may not be the feasible solution. Feedbacks are most welcomed as comment.