However, the methods described there that don't involve a domain validation step all specify prior ACME usage; that is to say that at least the first time you get a cert from an ACME CA with policies akin to those described here, you must always complete a DV step with DVSNI or Simple HTTP (which do require a publicly-visible server with a publicly-visible domain name).

What about the method in section 6.4: DNS? That certainly does not require either a prior ACME usage or a publicly-visible server.

That's a good point.

I don't expect the Let's Encrypt CA will be willing to help keep servers (or certs issued to them) a secret -- for example, the certs are likely to be published in Certificate Transparency! -- but you're right that the ACME DNS challenge doesn't require the server to be publicly accessible and doesn't even require the underlying subject name to exist in the publicly-visible DNS.