Before you rush into anything, firstly, your local domain name is just that, local. You can have a separate domain name on the Internet so why not follow that route?
To alter an ADs domain name does require removing the AD and reinstalling (or reconfiguring). We had to do this on two different servers and it did not take very long at all. However, you will lose everything that is in your existing AD, including computer and user accounts. I believe it might be possible to build a temporary AD on another computer, build a trust and then transfer the account details over, then repeating this for your new domain name but this is also fraught with dangers. I'll have a word with some colleagues of mine to see if they can suggest other ideas.
