You could verify ownership of the DNS config for the domain. It's not all that uncommon to verify ownership of a domain for various services by sticking something in a TXT record on that domain (or on a specially-named subdomain). LetsEncrypt could do something similar to verify top-level ownership. After all, if I have control over the DNS zone, then I trivially have control of any host on the domain too (just point the DNS at my own server).
Another benefit of this is ownership can be validated on an ongoing basis (is the TXT record still there? yup, still valid) without requiring any software to be running on any hosts at that domain. And you can validate a domain without even having an A record if you want (say, if you're getting all your ducks in a row before exposing your server to the world).
