Updating a car with a new key would fix both problems. Old recordings would be lost, of course, but customers hearing "I can't unlock that without your old key" may be necessary to re-establish trust.
Absolutely and that is why you can't use an HSM. Thankfully generating keys on device and storing them on the cloud account encrypted by a passcode works. As the keys are a predictable size you can encrypt them multiple times with different passcodes.