You do get in front of the other person and exchange public keys. Or you ask for help from a set of trusted middle-man. Those are perfectly fine ways to run a PKI, they are just not fit for the "entire web" PKI.
Those methods really don't scale by the fact that we haven't had a single system like that catch any popularity. It's usually just too cumbersome and not more trustworthy.