You'd just need your clients to give you a CNAME for the _acme-challenge. subdomain as well. That is, they'd set up a CNAME for service.example.com to you as they do now, as well as _acme-challenge.service.example.com to point to whatever DNS server you control (not necessarily on the same domain/server as the first one, perhaps this one using something like acme-dns).
Or, you could use HTTP-01 challenges instead, you'd just need your main web server to either support an API for handling the challenges that your central server talked to, or you could have the main web server redirect all /.well-known/acme-challenge requests to your central certificate server. Redirections are followed when checking challenges.
Be sure to check out the documentation on the challenge types if you haven't already.