SSL/TLS begins by a procedure called handshake, in which client and server agree on which cryptographic algorithms they will use (the cipher suite), and do some asymmetric cryptography magic to establish a shared secret, which, for the duration of the session, will be used to do symmetric encryption and integrity checks on subsequently exchanged application data.
Usually, the "key exchange" bit assumes that:
- the server sends his public key as part of a certificate (as specified in X.509);
- the client validates the certificate with regards to his own set of trust anchors (aka "root certificates") to make sure it is genuine, and contains the public key of the intended server;
- the client uses the server's public key to do the asymmetric key exchange, normally by encrypting a random string with the server's public key (the server will use his private key to decrypt it back)(I am skipping over details irrelevant for this answer).
The hard part about a server certificate is that the server needs to have his public key in a certificate which the client will accept. Since the client accepts certificates based on their signature, to be verified against a finite set of a priori known public key (the keys of the "root certification authorities"), a certificate apt for validation may be obtained only by asking the said certification authorities. Most CA will do this only at a price (StartSSL will do it for free). Things are simpler if you control the client code, because you could add your own "root certificate" in the client, and, in effect, manage your own CA and issue your own certificates. This is still key management (the dreaded Public Key Infrastructure), and, as such, entails a non-zero cost.
You can do "certificate-less" SSL in two ways:
You can use one of the "DH_anon" cipher suites. These are cipher suites in which both client and server agree that there is no certificate at all; key exchange relies on Diffie-Hellman key exchange. Most client implementations (read: Web browsers) can support that, but it is very often deactivated by default.
You can have your server send his public key as a fake certificate. A certificate is just a container format; as long as you put a sequence of bytes of approximately the right length in the "signature" field, it will fit the format (traditionally, we use "self-signed" certificates -- as if the server was its own CA -- but any sequence of junk bytes will do). Of course, the client will no longer be able to validate the certificate. Web browsers will loudly complain with scary warnings.
You may note that while a Web browser will shout and scream at the sight of a self-signed certificate, it will also allow (after clicking a few times on "I know what I am doing" buttons) to install an "exception", by which the client accepts to use that unvalidated certificate. The good part of the exception is that it can be made permanent: the server stores a copy of the offending certificate, and, the next time the client connects to the same server and the server sends back the very same certificate, the client no longer complains. With an installed exception, there is a window of weakness (namely, when the user decides to "install the exception": at that time, he does not really know whether the certificate is the right one, or that of a meddling attacker), but afterward the security is restored.
(It is still an idea of questionable quality, to train your users to bypass the scary warnings by installing exceptions.)
Putty is not a SSL client; it uses the SSH protocol, which is conceptually similar to, but practically distinct from, the SSL protocol. The SSH protocol is certificate-less, because it relies on the same model than what I described above with self-signed certificates and installed exceptions. The first time you connect to a given server, the SSH client (Putty) will ask for confirmation before accepting the server public key, normally displaying the "fingerprint" of the public key (a hash value) so that you may compare that fingerprint with the expected value (that you know "out-of-band", e.g. you learned it by heart, or you phoned the sysadmin and he spelled it out for you). The SSH client will then permanently record the public key, and not ask for confirmation anymore -- but if a given suddenly uses a different public key, the SSH client will wail even more loudly than a Web browser confronted to a new self-signed certificate.