Besides using a certificate to defend against a man in the middle attack
during a key exchange, what methods can be used?
Any shared secret can be used. Securely distributed passwords and symmetric keys, for example. Alternatively, you can use asymmetric cryptography, such as public keys.
For one example, SSH has for years authenticated servers using public key cryptography and users typically using either public keys or passwords. Only recently had SSH added support for certificates.