If, instead of identifying services by some human readable name, they are identified by their public keys, then we don't need certificates - there are several encrypted and authenticated transport protocols which only require knowledge of the destination's public key upfront.

You then need an alternative name system which links a unique human readable name to a public key. This is the tricker part (see Zooko's triangle), but there are some creative solutions like Namecoin and the Blockstack Name Service.