I worded my post incorrectly which confused you slightly, apologies Matt
What James said is correct, you will be able to change your NS whilst the VPS is still available, your site will still be accessible to all users if their NS hasn't updated which should take around 24 hours.
So you shouldn't face any downtime whatsoever