I would recommend python's Fabric for this purpose:
#!/usr/bin/python
# ~/fabfile.py
from fabric_api import *
env.hosts = ['host1', 'host2']
def deploy_script():
put('your_script.sh', 'your_script.sh', mode=0755)
sudo('./your_script.sh')
# from shell
$ fab deploy_script
You should be able to use the above to get started. Consult Fabric's excellent documentation to do the rest. As an addendum, it's totally possible to write your script wholly within Fabric -- no copying needed, however it should be noted that to change the script on all machines, you would only need to edit the local copy and redeploy. Furthermore, with a little more than basic usage of the API, you can modify the script based on which host it is currently running on and/or other variables. It's a sort of pythonic Expect.