I know Google can find domains by checking with registrars, but is it able to find new subdomains with no backlinks?
I suspect they are able to by checking DNS records, but can anyone confirm/deny?
Hard to say without doing case study, I will say Google will find out those pages if they consider them as popular/important pages (If those pages are getting zero visits then I will say Google will not going to gather any information from anywhere), so to do case study, create simple landing page and block that page via robots.txt so Googlebot don't crawl it then redirect your all visitor to subdomain (Actually you should not taste subdomain, instead test any webpage like example.com/secreat/xyz.html and don't link them anywhere, not in sitemap as well)).
But I think Google will index your content because Google may already using their product info (Chrome user history, Google public DNS etc) to index popular/important content.
We all know nofollow links are not crawled by Google directly. So whenever any user share any information to social media(Which use nofollow tag on all links), and if many of visitors read those content, then I confirm that Google will index that page faster, without checking your sitemap/links first.
Web are too big now, they may already implement many of crawlers other than based on backlinks, and Pagerank.
Google does not share so much information about crawling/ranking compare to 2003 - 2007, so can't confirm anything.