I would recommend using a mixture of Debian pre-seeding, where you give the installer a text file that answers all the questions it would ask, and Puppet.
THe reason for using the preseeding, rather than FAI is that you don’t have to set up an image first and deal with keeping it up to date. You will end up with an install very similar to what you would have if you did them all by hand. When you come to install a new release, you will have to update a config file with the changes, rather than having to rebuild a new image.
A configuration management tool is particularly useful where you have several servers performing the same role and you want them to be identical, e.g. webserver cluster. However, they can also be useful for configuring the base install of all servers. You’re going to want to install particular packages on all your servers, like ntpd and a MTA. You’re going to want to change a config file on all your servers. An additional benefit is that you can keep your manifests in something like subversion and keep a record of what changed on a server and who did it and why. Configuration management can also be a life saver in the case of a server failure and you need to rebuild it quickly. Install the OS (using FAI or preseeding), install puppet and away it goes, built back exactly as it was before. Obviously you’ll need to keep backups of data.
Configuration management requires dedication to make sure you only make changes using it and will have an upfront cost setting things up, but once you have a working setup you won’t regret it.
Puppet is the more modern of the two tools you’ve mentioned. I really recommend it to anyone. The configuration is a declarative language and is easy to build up higher level constructs. There is also a very large community around it and there are always people welcome to help on the mailing list or the IRC channel.