It gets rather sickening to do these by hand, especially for large clusters, so I wrote a package to handle performing rolling restarts and upgrades for you. Thought I'd drop a link to it here in case it could help anyone out.
We use Salt to deploy our clusters, so this is somewhat attached to that for now, ie it's how we restart the service after hitting the shutdown API. That said, it's very easy to modify it to add in a different method.
Github is here (also on PyPi): https://github.com/vertical-knowledge/rollastic