So the problem I have with this is that it collides with using Puppet to manage your users--Puppet will have to know about the users' Unix passwords.
It should be fairly straightforward to write a script that tests for SSH keypairs with an empty passphrase, simply try to authenticate an SSH agent by loading the user's key.
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.