Basically, the solution you're looking for is going to involve some sort of offline transfer. The two computers that are the endpoint nodes of your secure tunnel must be "introduced" to each other, exchanging some secret that will allow one side to initiate a connection in such a way that only the other node could understand it.
While this shared secret could be the symmetric key in itself, this can be problematic; symmetric algorithms are most secure when nothing about the key is known, even the fact that it's the same key as was used for another communication. An attacker could watch multiple "conversations" between the nodes, and if he knows the conversations use the same key and IV, and if he can guess the plain text (which he is likely to do as the information sent in the initial stages of communication is fairly boilerplate), he can use the ciphertext to reverse-engineer the key. For this reason, the symmetric key must be renegotiated often, even on the same secure channel, depending on how much data is sent across.
The go-to solution is asymmetric or public-key cryptography. Understand one thing; public keys are meant to be public. You could spray-paint your public key on the side of your car and drive it through Black Hat or DEF CON, and all anyone could do is attempt to connect to your endpoint securely (which is no more than they could do to any other TLS-secured endpoint, and they wouldn't get far here; keep reading). The private key is needed in any public-key scheme in order for data to be decrypted efficiently (and thus for information to be at risk).
Now, you may not publicly distribute this certificate; you could, quite plausibly, implement a simple variant of the basic TLS scheme where the normal first step, the client's request for the server's certificate, would be ignored by the server. Instead, the client must already have a certificate for the server "pinned" in the OS certificate store, and would not (could not) verify it had the latest version. It would then be able to negotiate a secure connection without a single bit of actual data being sent plainly (the packet data would still be in a well-formed IP packet).
Conceptually, it would work as follows; the client would have the public key of the server, which it was given offline (here, the only difference between "client" and "server" that we care about is that the client is the one initiating communication; both computers can be "servers" in other senses of the word, such as file servers in the cloud). The server would have the public key of the client, which it received offline. The client encrypts a request using the server's public key, which will contain the client's certificate. That request goes to the server IP, and only the server can decrypt it, even if someone else were sniffing or spoofing traffic on that same IP address. The request can contain a nonce, such as a simple counter value, preventing replay attacks (the server can ignore multiple requests from the same client with the same nonce, though it must decrypt each request it receives to determine this, which could make it vulnerable to DDoS).
The server would then use the client certificate, which it can independently verify as an authorized client because an exact copy of the client cert lives in the server's OS store, to send a symmetric key negotiation. From this point the scheme is virtually identical to two-certificate TLS negotiation; the server sends the client the key negotiation request, the client receives, sets up its cipher, and returns either a symmetrically-encrypted acknowledgement or the other half of the key-exchange protocol so the server now knows they're talking the same language. From then on, client and server can communicate using the symmetric channel. All this, without a third-party observer seeing any packet data in plain text.
Now, this is just to create a secure channel. Even if the client node has a static IP, it's always good to subsequently verify, after negotiating the secure tunnel, that the human controlling the computer on the other end is someone authorized to use the system. Credential exchange like username/password, or the entry of a time-limited key value generated by a fob, are common and perfectly feasible means to authenticate the user of the authenticated computer(s).
