You are right, deleting certificates is not possible. Although you can remove them from your ELB but you can't delete them and ELB can continue to use them, so the safest option here for you is to delete the ELB and make a new one. use the following command to delete the ELB associated with certificates:
aws iam delete-server-certificate --server-certificate-name certificate_object_name