After some time passed, I was able to delete the certificate. It seems that deleting the API Gateway was indeed the cause of the error, and it simply needed some additional time to pass after deletion before I could delete the associated certificate.
From your question I have understood that you are unable to find an ACM certificate and the associations with it. You were correct that to delete a certificate that is in use, you must first remove the certificate association. This can be done using the console or CLI for the associated service. I will link a general guide below: https://docs.aws.amazon.com/acm/latest/userguide/gs-acm-delete.html
Yep API GW edge-optimised APIs are accessed through a CloudFront distribution you don't own - it's in an AWS-managed account. It will use your cert though as you've seen. "aws apigateway get-domain-names" can be used to see the distribution domain names.
How to provision CloudFront distribution with ACM certificate in CloudFormation?asked 9 months ago
Certificate associated with Cloudfront does not resolve to an IPasked 3 years ago
Certificate is associated with an arn:aws:cloudfront:::xxxxx/xxxx that cannot be foundasked 9 months ago
Unable to delete certificate - in use by an unknown accountasked 3 years ago
Inability to delete an public ACM certificate, resource in useasked 8 months ago
Unable to Delete ACM Certificate - No API Gateway, Custom Domain or Cloud Front Distribution Existsasked a year ago
Unable to delete ACM certificateasked 7 months ago
Unable to Delete ACM Certificate and unable to open a ticket to AWS support (basic account)asked 8 months ago
Can't Delete Certificate Due to Load Balancer Associationasked 10 months ago
I can't delete my certificate because it's associated with an invisible cloudfront distributionAccepted Answerasked 4 months ago