Well, you have them create a DNAME that maps theirhostname.theirdomain to yourhostidorsomething.yourdomain, and then you have in your nameserver A and AAAA records for yourhostidorsomething.yourdomain and a TXT record for _acme-challenge.yourhostidorsomething.yourdomain!?

(Obviously doesn't work if they are to keep control over other subdomains of theirhostname.theirdomain, and also, I haven't tried it with DNAMEs, so I don't know whether their implementation is buggy.)