I'd write a script to modify /etc/resolv.conf using my favorite scripting language of choice and execute it on each remote machine w/ SSH.
Assume the old DNS server is 192.168.1.1 and the new is 192.168.100.100:
perl -pi -e's/192.168.1.1/192.168.100.100/' /etc/resolv.conf
Just execute that on the remote machines using SSH and you're golden. (Hopefully you have certificate-based authentication set up so that you're not keying passwords to connect to each host.)
Edit: On a Windows box
The "netsh" command is your friend. Assuming the network connection still has the name "Local Area Connection", you can do:
netsh interface ip set dns name="Local Area Connection" static 192.168.100.100 primary
That will set the primary DNS server specified on the connection "Local Area Connection".
If the connection has been renamed then you're probably best off dumping the configuration with
netsh interface ip dump, parsing that output, and using netsh to make the necessary changes.