I can't speak to puppet, but I would expect the proper thing to do is to run puppet as root, or possibly create a puppet user with NOPASSWD if you must. There's really no reason to not run as root if you're going to run NOPASSWD ALL, since anyone with the slightest bit of deviancy in mind (or just annoyance with not being root) is going to "sudo su -", and sudo is done.
You can probably write a script that searches for empty-phrase keypairs, but this would be a client side thing. The private key is not disclosed to the server, and all operations involving the private key happen post-decoding, so this is unenforceable server-side. It would be an interesting policy/hygiene enforcement tool but would be of little or no use for security purposes.
What I mean is that in order to manage user accounts, the management tool (Puppet) will have to know what the encrypted password is so it can insert it into /etc/shadow. Otherwise you have no password and must rely on NOPASSWD in sudoers if you want to log into that managed machine and use sudo.
If the system doesn't have a password for you in /etc/shadow, sudo can't authenticate you via getpwent or whatever.
So your only two options are to write a tool for users to update their password in Puppet directly/indirectly, or allow NOPASSWD and religiously check for empty passphrases on SSH keypairs.
You can probably write a script that searches for empty-phrase keypairs, but this would be a client side thing. The private key is not disclosed to the server, and all operations involving the private key happen post-decoding, so this is unenforceable server-side. It would be an interesting policy/hygiene enforcement tool but would be of little or no use for security purposes.