Well unfortunately I don't know another company has their nameservers on it, and I know I could do it by an mx entry in plesk if I had the nameservers changed, but the customer cannot afford any down time in their email service.
If an mx entry can be done to change email service, couldn't the reverse be done for hosting?
Depends on when you ask "without changing nameservers completely" or "without changing nameservers to new webhost nameservers."
find out new nameservers IP addresses and create new custom nameservers of your own and wait for their propagation. Once they are available can be confirmed from www.internic.net/whois.html you can switch to new custom nameservers.
Name123.com [ We are online Since 2004! ] Cheapest Domain Registration & Reseller Services! ENOM Domain Reseller Account with Lowest Industry Prices! (Details) Plus Excellent Technical Support Along The Way!