How can we exchange public keys between two servers in a secure way?

This will mean a lot of unneeded overhead. I'd suggest following:

• Since you don't have certificates issued by CA, create your own CA. Namely, create a self-signed certificate and add it to a key store on both servers, so that your certificate is trusted.
• Issue certificates to each server and sign them with private key of your own CA.
• Make your servers use their certificates when communicating with the others.

Thus you will actually use PKI.

In the future, when you get certificates from the real (commonly known) CAs, the only thing you will need to do will be to replace your own self-signed CA certificate by (also self-signed) certificate of a real CA.

No, I don't think that the solution is good. Let’s go through it:

1. This is fine
2. If we can manually copy, why not copy the public keys directly?
3. Here's the real problem. As this is done on an insecure connection, you can't be sure that the first server actually talks to the second server.

You weren't specific on how the exchange works, but using the token as simple API authentication token will not prevent a MITM attack.

In the communication between the two servers, an attacker can:

• intercept the token when the first server sends it, forward it to authenticate & send a fake public key to the second server
• send a fake public key to the first server in place of the real one from the second server

Or visualized:

A  ------ token ----->  E  -- authenticate with token --> B
A  <-- fake pkeyB ----  E  <------ real pkeyB ----------- B
A  --- real pkeyA --->  E  ------- fake pkeyA ----------> B

You seem to want symmetric key crypto, maybe something like Kerberos. But for the use-case you describe, copying the keys manually seems easiest (or exchanging them insecurely and manually checking the received keys fingerprint).

The only way to establish initial trust between two servers separated by an untrusted network has to involve a manual¹ step. This can be achieved either by copying it manually or by manually comparing whether the keys are transmitted correctly before trusting them. The manual comparison is typically done using a key fingerprint. It can be done by comparing a secure hash (like SHA-256) of a copied file as well.

There are other ways, but they must involve transporting a piece of information between the two servers, there's no way around it. It can be proven mathematically. Copying the key via untrusted connection and comparing a fingerprint manually is the most straightforward way, in my opinion, and also fairly standard.

Note that for a network of servers you only need to transport one key per server added to the network, for a total of N - 1 such operations for a network of N servers. If you wish to add server X to a network of servers A, B and C trusting each other's keys you only need to establish initial trust between X and, for example, A. Trust between X and B and between X and C can then be established by means of key signing.

---

¹ The word manual here was used for simplicity. What is essentially meant is that a piece of information must be sent from one party (server) to another through a trusted channel. This trusted channel might be the operator driving to the server with key fingerprint written down on a piece of paper as it might be a trusted cable connection. Furthermore for a connection to be trusted in the context of public key exchange it only needs to be resistant to man-in-the-middle attacks, or, in other words, it needs to preserve the integrity of the message. Potential eavesdropping of the connection doesn't harm this trust, as all such an attacker could learn are the public keys.