Hi,
The way I see it is that if you take care for the certificates, than all the other steps are real easy.
if you check the centralized puppet infrastructure page at
http://reductivelabs.com/trac/puppet/wiki/PuppetScalability, you could design a puppet master who signs other puppetmasters certificate.
and than you could tell the clients to trust any puppet master which was signed by the root puppet master, making its unnecessary to sign all clients again.
in our environment we build puppet masters by another puppetmaster.... and then the only thing we need to change is the dns entry.
Cheers,
Ohad