I'm assuming mrkurt meant that you send your users once to create a dns record (in case you haven't already) - you can add any hostname you want on Fly, it doesn't have to exist, yet. Then you go and create a DNS challenge for Let's Encrypt. Obviously, these 2 steps are orthogonal, but this is the reality of user onboarding.
Well, it's two DNS entries. You could do them both at the same time, but people were getting that TXT record wrong pretty frequently, which would have meant https connections getting an invalid certificate had they changed their actual hostname at the same time.
Since we control the http response once DNS changes, we don't have that problem. And it's simpler for people to create CNAME/ALIAS records.
Erm ... you had people create TXT records? Why would you do that? Wouldn't people then have to manually update the TXT record on each certificate renew?!
Why not have them create a DNAME, a delegation, or just two CNAMEs?
This is an often overlooked option, but you can indeed solve the DNS challenge by having someone create a CNAME record for _acme-challenge.example.com that points to a domain under your control, and then serve the TXT record needed to verify the challenge from that domain. acme-dns[1] provides a nice implementation of this idea, as well as a more detailed explanation.