We use puppet and add our public keys to all servers. IMHO a nice solution, but clearly a lot of work without something like puppet.
We have a simple Puppet recipe that creates a user, group and home, sets the correct permissions/groups and installs the public key. It will also remove users if they leave the company.
The script reads all users' details from YAML so if there are any changes, we push the YAML to all servers and run the script. It's not as automated as Puppet-Agent, but it's fine for a small number of servers.