It IS possible but I agree with Norm. the process is difficult and 1 false move and the domain is toast.
Here is a link on how to do it.
http://technet.microsoft.com/en-us/windowsserver/bb405948.aspx
Please not that this is for a Windows 2003 domain. If you have any 2000 acting as domain controllers you will not be able to do it without rebuild the entire domain.
As far as getting mail to appear as it's coming from the correct domain, that's easier. Just add that domain name to the exchange server and make it the default domain.
Since you have so many servers, including SQL servers I would do everything I could to not have to rename the entire domain. Try to make the powers that be understand that if the rename goes wrong they run the risk of losing access to all of these servers for however long it takes you to correct it. From personal experience I can tell you that at the best you'll be working for at least 60 hours straight and will be on the phone with Microsoft for many of those hours as the servers misbehave.
Good luck