I have 2-3 node clusters for our load balancers and various web applications. I'm having to make the change in QA first, then in staging (on 2-3 servers), then in production (on 2-3) servers. Is a configuration management tool like chef or puppet appropriate here? Or is it overkill? If it's overkill are there any tips to making this easier.
Not overkill at all. Start using puppet now, and it'll pay for itself in the long run. Seriously.
I use puppet even if i'm only deploying one server, because I know at some point it'll probably have to be replaced, rebuilt, or another one added as a backup.