Exception is maybe the credit card number, but that would mean that only a small subset of the original account holders can change their password.
Or you use a PS3 device ID and only allow changing the password on the device, but that is also known by the attackers and I'm sure it could be spoofed.
Not even sending a token to the email address on file would work in all cases because the users might have lost their email accounts to the breach too (by reusing the same weak password).