На данный момент я не очень много управляю серверами (менее 10), поэтому я не могу вам чем-то помочь, но если проблема масштабирования, вы можете развернуть без мастера, используя git и запустив puppet with cron (http://current.workingdirectory.net/posts/2011/puppet-without-masters/).
Вам просто нужно развернуть конфигурацию, используя cron (и выбранные вами vcs), и применить ее, используя также cron (или fabric, или mcollective).Тогда единственное, что нужно масштабировать - это сервер vcs, а это гораздо проще сделать.Вы даже можете просто использовать rsync или nfs, и я думаю, что обслуживание нескольких тысяч серверов не будет проблемой.