This answer is inspired by my conversation with MechMK1 in the comments. The problem that MechMK1 points out in the comments basically boils down to authenticity
, which is often seen as the achilles heel of public key cryptography. How can you be sure the public key purporting to belong to the person that you are attempting to connect with really belongs to that person, and not an MITM?
One way to verify the authenticity of the other party's public key is to use use an out-of-band channel, such as SMS, fax, phone, postal mail, etc.
But, as MechMK1 points out, it's possible that the attacker may be able to intercept connections in these other bands as well. Not many attackers have the ability to this, but it's not out of the realm of possibility for a three-letter agency or a nation state. In this case, sneakernet (exchanging public keys in person) may be the most secure way to verify the authenticity of the other party's public key, if possible.
But, if sneakernet is not an option, due to proximity, time constraints, logistics, etc., then another option is to use a trusted third party, who's public key we know, to verify the authenticity of the other party's public key. This is what SSL/TLS does, using certificate authorities (CA's). PGP does this using a web-of-trust model.
But we know that neither of these are perfect solutions. Perhaps the most notorious example of this was the incident involving the CA DigiNotar in 2013.
Moreover, if the CA or trusted third party is not able to verify the authenticity of the other party's public key in person, then the CA or trusted third party must connect to the other party through some network. If the attacker has as much reach as we are assuming for the sake of this question, then the attacker can simply MITM that connection as well.
To summarize, there is no perfect solution to this problem.