The customer is wrong here and does not understand what they're talking about. Changing the passphrase on a private key is a very bad idea, because it has very counter-intuitive security properties.
Normally, users think of passwords that they have changed as "no longer secret". They might become throwaway passwords for low-value sites, online handles/nicknames, punchlines to jokes, etc., and any paper on which they're written might become scrap that's exposed.
For a passphrase used to encrypt a private key , that's not how it works! The passphrase must be kept secret forever unless all privileges associated with the key have been revoked (and the following doesn't apply to ssh keys, but if the passphrase is for a key used not just for signing, but for receiving private messages, then forever really means forever). This is because of the possibility that the encrypted private key file has been obtained by an attacker or stored somewhere (like in a backup) where it might be obtained by an attacker in the future. If the passphrase is ever revealed, it's then compromised.
In some sense, a private key that has gone through N passphrases in its lifetime is 1/N as secure, since knowledge of anyone one of the past passphrases is sufficient to compromise the key if the attacker has had access to the encrypted private key file.
Now, back to your problem.
If the customer had not latched onto this "ssh passwords" misconception and dug in on it, the right thing to do would be just never bringing it up to them, and follow best practices for key handling yourself. But now that they have, you probably have to do something to satisfy them. You could try explaining how passphrases encrypting private keys have different security properties from passwords, but given how wrong the customer is about a lot of things here (password expiration is a bad idea in general) I doubt that's going to work.
That leaves you with the task of automating a system for distributing new keys. I would strongly discourage you from automating a system of generating the new keys centrally, since private keys should never be moved between machines. Instead, you should have processes/reminders/scripts to make it easy for the employees/contractors on your side who need access to generate new private keys and publish the corresponding public keys, and have the public key distribution system (Puppet or otherwise) that you use push these out to the systems they need to access.
In addition: One thing that might convince the customer to drop this is mentioning that there is fundamentally no way to enforce that the new private key have a different passphrase than the old one, or even that it have a passphrase at all.