It seems like you can make a good tradeoff between Chef and AMIs by nightly rebuilding the AMIs off a fully configured system, and then when the machine comes up you run Chef to make up the incremental difference.
Yep! You could also build the AMI's using a build / CI server each time you push if you wanted. Once you've nailed the process and are used to how long it takes you'll love it.