Diffie-Hellman is fine if there is no one between you and Alice, otherwise if you read the protocol you will see it is easy for Eve to do the protocol with both ends and just act as a conduit for messages after reading/altering them.

SSL/TLS relies on trusting a number of certificate authorities to verify that, yes, the other end is Bob. Note that for this to work securely you must already have their public key info. There are problems with this also but it's the best we have got right now.

There's the interlock protocol that ensures that you'll only be talking with one other party instead of one other and one in the middle but still you don't know who you're talking to.

But it's impossible to identify someone out of nowhere. Even in physical life we need external information of a person or an organization we don't know to identify him.

So, we will always need some leads with which to cross-check the other party's identity. And given that, there are plenty of protocols to exchange symmetric keys securely.

But that's exactly the problem, that there is no way to securely verify over an insecure connection that the keys you've associated with A are actually A's keys.

That's really a non-problem since how could you ever know?

The only way to verify that A's keys are legit is to use a secure channel first. Then you can leverage that over any number of insecure channels later to reconnect with A.

In the end, security all comes down to trust. It is rather hard to get 100% trust without establishing it outside the system (PGP key exchange, SSL/TLS certificate authorities).