The client says "Hey, i have a cert here, and I want to verify i control domain.com"
The server says "Ok, take this [set of challenge data], encrypt it with your cert, and put it at .well-known/acme-challenge."
The client takes the challenge data. encrypts it. puts it at the challenge point and informs the server.
The server verifies that the encrypted data matches what they were expecting to get. They then sign the cert because only a person with the webserver/domain and the cert could pull off this magic.
The important part here, is that since the client already has the cert in hand when the verification is taking place - it can be used as part of the verification. Use the cert to do cert stuff. Only that cert can do those things. If I can't even get a cert until AFTER I've proven I control a location, then this obviously doesnt work and another "proof" has to be made - hence godaddy's issue.
Why isn't that good enough? No need to use a cert to verify it.
Let's Encrypt is meant to be renewed by cronjob, and most web servers probably don't have programatic control over their DNS records.
The difference between "prove you own this domain and we will provide you a signed certificate for it" and "prove you own this domain and this certificate at the same time, and we will sign it for you"
It's really not that different, except they have opted to make it such a way that it is easily automated. And it's open source, so if they wanted to google, amazon, or even godaddy could set up an ACME server that validates SSL/TLS certs... but would they be able to charge for it if you had to use the lets-encrypt process anyway?
ACME uses public key cryptography in (at least) three separate places, the keys pairs are different in each place. Like completely different - one could be 2048-bit RSA, one could be a shiny Elliptic Curve key, and one 4096-bit RSA.
1. Access to HTTPS ACME service over SSL/TLS. Let's Encrypt has a private key, users of their ACME service get a public key, this allows them to be confident they are dealing with the genuine Let's Encrypt ACME service
2. ACME accounts and associated challenges. Every would-be subscriber using an ACME service must create an account, this account has a private key (which they know, usually stored in a file on their computer) and a public key, which they send to the ACME service.
The ACME private key is used to sign data in ACME challenges. This proves that whoever is passing the challenges (e.g. by putting files on a web server) is also making the ACME requests. This provides the confidence to issue certificates to the account holder.
3. The SSL certificates have a public key baked inside them, which corresponds to a private key owned by the subscriber. The subscriber proves they control the private key and want a certificate by signing a Certificate Signing Request, CSR with their private key.
The Certbot software often used with Let's Encrypt automates most of this, making the key pair for (2) automatically and just requesting you OK a PDF describing the rules for Let's Encrypt. By default it will make the key pair for (3) as well BUT if you're getting a certificate for some device that issues its own CSRs, you can hand over a CSR and it will use that one. If it didn't allow this, you couldn't get the right certificate for a device that only issues CSRs, because those devices provide no way to upload a different private key.
Finally, we expect that third parties will want to offer ACME services where a mandatory challenge is like "Fax us all the paperwork and pay $50 verification fee" and then you get an EV certificate instead of the DV certificates that Let's Encrypt issues. Also, never underestimate the willingness of big businesses to pay money for things.
You are correct that Let's Encrypt don't generate the subscriber's key pair. This is (or should be) true for every public CA offering Web PKI certificates today. The subscriber puts their public key in a Certificate Signing Request, and signs it with the corresponding private key. Let's Encrypt receives the CSR, verifies that it is correctly signed, establishes that the requesting Let's Encrypt user account is authorised for all the DNS names listed in the CSR, and other parameters are acceptable, then it creates a signed certificate for those names, with the public key from the CSR.
[Edited to add: If you use Certbot or similar to just issue a certificate all the CSR creation and signing is done for you. But it still happens, and Let's Encrypt are still the ones actually making and signing the certificate]
It is essential that Let's Encrypt create the certificate. Under the current Baseline Requirements they're obliged to ensure that the serial number is unpredictable yet unique across all their issued certificates. The only practical way to achieve these goals is for them to create the certificate from scratch and sign it.
The situation where a tbsCertificate (the certificate document before it is signed) is transmitted anywhere is unusual. The only example I can think of recently was where Symantec were arranging SHA-1 exception certificates and Google's process deliberately involved showing everybody the tbsCertificate before it was signed so that we (the community) could examine it and ask for anything unusual to be explained. If you go back and look at those discussions you'll see it was me who first asked for the weird OU value in certificates for TSYS to be explained or removed -- they were subsequently removed before the certificates were issued.