How can CloudFlare provide a valid SSL certificate for domains not under its control?

Simply put, the webmaster of the site uploads the certificate to CloudFlare.

See this article for details.

The Keyless mode doesn't have this requirement. It uses an on premise key server instead, to provide the private key of the server. See the diagram here for details on how this works.

For free accounts

Cloudflare state in their blog:

For all customers, we will now automatically provision a SSL certificate on CloudFlare's network that will accept HTTPS connections for a customer's domain and subdomains. Those certificates include an entry for the root domain (e.g., example.com) as well as a wildcard entry for all first-level subdomains (e.g., www.example.com, blog.example.com, etc.).

Cloudflare do control the domain, because the customer has pointed their DNS records to it, this means that they can gain a Domain Validated certificate. Domain validation procedures do not have to involve sending an email to the domain, which wouldn't be possible for Cloudflare to intercept because the MX record is not repointed. They can instead prove that they own the domain by putting a randomly named text file containing a random key for the CA to query in order to prove control of the domain. The CA will specify the name and contents of this file that they will then be able to check. Cloudflare could then intercept requests for the URL and display the necessary validation code.