Unfortunately, there is no simple solution to your customer's problem.
The customer does not have admin credentials
The person with admin credentials is no longer with the company
You do not have delegated admin access to the customer tenant
There are no other administrators
As far as I know there are only 3 options left.
First is if the customer knows someone in Microsoft's senior leadership team who can assist by internal escalation
Second is if the customer purchased the license from you, and you purchased it from a distributor who is willing to use a premium support ticket to assist in an account lockout situation. I hear that Pax8 has such a policy in place if you purchased it from them.
Third is have the customer call Microsoft Support line by phone. However the customer might need to have their proof of ownership information ready such as tenant ID, previous administrator details etc. Else they would appear to be a random stranger on the phone asking to unlock a Microsoft tenant.
These phone numbers have Interactive Voice Response agent (IVR). Due to phone connection quality, and also your accent, some people have feedback that they have difficulty talking to a person. So using a good phone line, speaking slowly and clearly, might be an important factor.
Others have feedback that following this script might be helpful
IVR: What kind of problem are you concerned about?
You: Authenticator.
IVR: What kind of product do you use?
You: Office 365 for business.
IVR confirmation: education or company account?
You: For companies or For education
IVR: Are you an administrator?
You: Yes.
IVR: Do you have the other administrator in your organization?
You: No.
IVR: Do you need a... Service request?
You: Yes
Hope this helps