Skipping over the fact this was a poorly designed implementation and bad choice of network scope from the implementation...
All facilities, even hospitals, can plan for downtime... I just did a 600+ phone hospital, including 4 remote clinics and also the ER/Trauma center for the local county, cut-over to a new system AND simultaneous telco switch, there was downtime, but it wasn't a problem because it was planned for properly.
Still here is one possibility, taking what you say to heart with zero downtime... build a new VLAN and deploy the new scope in that VLAN and change/implement your LLDP settings to put phones into that VLAN (remember this will only occur at boot of the phone, so existing phone will not be affected). Once it has been tested and verified functional there are many options to move all the phones to that VLAN, reset individually, reset switches, bounce ports in the switch, etc. Now you have a new VLAN for just voice (except the 5000, but properly implemented shouldn't be a problem), and you opened a whole bunch of your default data VLAN for other network devices.
In my opinion, the best practice here would be to plan a maintenance window and move the entire voice network into a new VLAN, including the 5000, for example into a 172.16.xx.xx subnet with ample room for growth (2-3 times projected 10 year growth), move the phones, 5000, and any other UC servers/services, into the new VLAN, and make a quick change to the other 16 nodes to talk to the new IP address. Again, with proper planning, testing, and implementation, you are still looking at minimal downtime at least for critical areas. You have also "future proofed" your VoIP network for unknown growth.
Also remember you are networked with 16 other sites, so it might be a good idea to get a little conference call going with system/network administrators at other sites to make sure just arbitrarily picking 172.16.16.0/22 for your VoIP network won't mess up some other implementation or plan for the future.