If you really want to make it funked out, you could set up a CI process to check out your puppet scripts and build an AMI whenever a change is made to your config. Then the deploy task would be a rolling upgrade of the new AMI to whichever environment you want the config to affect. With some cloud formation and puppet trickery you could also one-click-bootstrap new environments (e.g. "production in region x", or "staging in region y") and just run the deploy task to that new environment.
Since you're already using puppet, which is great at keeping existing instances up to date with config changes (it's almost the whole point), wouldn't it be better for your CI to create those AMIs asynchronously when you deploy, but not actually use them unless you (or autoscale) are launching new instances? Just use puppet to deploy config changes as usual, then have the AMIs at the ready, rather than immediately recycling your instances with the new AMIs. This should be much faster (and more loosely decoupled from AWS).
