Nonces do not require secrecy. The virtue of a nonce is to occur only once, not to be unknown to outsiders. The fact that the client random and server random are sent as cleartext does not prevent them from being "nonce".
The actual "nonce" is the concatenation of the client and server random. This is explicit in several places, especially in section 6.3 of RFC 5246, which deals with key computations: the symmetric keys used for encryption and MAC of application data are derived from a combination of the "master secret" and the concatenation of both randoms:
key_block = PRF(SecurityParameters.master_secret,
"key expansion",
SecurityParameters.server_random +
SecurityParameters.client_random);
The two random values will also occur in the computations for the CertificateVerify and Finished messages, since both use a hash value computed over all the previous handshake messages, which includes the two "hello" messages and the random values they contain.
So the client random protects itself by sending a new client_random: whatever happens on the wire, the client will use the random value it sent for key computations. Similarly, the server protects itself with its server_random. To see how the protection works, consider a replay attack: the attacker observed a handshake between a client and a server, and then wishes to replay the same handshake with the server, thereby impersonating the client. The attacker observed this:
ClientHello (ch1) --->
<--- ServerHello (sh1)
Certificate (c1)
ServerHelloDone (shd1)
ClientKeyExchange (cke1) --->
ChangeCipherSpec
Finished (cf1)
<--- ChangeCipherSpec
Finished (sf1)
The attacker then connects to the server, and sends an exact copy of the ClientHello (ch1). The server, however, responds with a distinct ServerHello (let's call it sh2): that ServerHello is very similar to the one used previously (sh1), but with a new server_random value. The attacker can then proceed with the handshake, but things will fall apart when the attacker sends the Finished message cf1: that message should contain a hash derived from all previous handshake messages, and be encrypted with keys derived from the master secret (that the attacker does not know, he merely "replays") and from both client and server randoms. For both computations, the server expects the Finished contents and the keys for encryption to have been derived using the random from the ClientHello and from its own ServerHello (i.e. here the "sh2" message). The "cf1" message won't match, since it was computed with hashes and keys from the initial handshake, with the randoms from ch1 and sh1, not sh2.
The recorded packets cannot be all replayed by the attacker because, by definition, the attacker replays only half of the conversation. When the attacker tries to impersonate the client, he can send all the packets on behalf of the client, but must work with what the genuine server responds (if the attacker impersonates both client and server, then he can do a "perfect replay", but he is actually talking to himself only, so this is considered a mental illness, not an attack). The server_random thus enforces a divergence which thwarts the replay attack.
(A similar case can be made with an attacker trying to impersonate the server when talking to a genuine client: the client_random protects the client against that replay attack.)
Alternative description: the client and server actually do verify nonces. They do so implicitly when they compute the symmetric keys, and check the contents of the received Finished messages. The client won't be content with a received Finished message from the server unless that message was computed and then encrypted using (among other values) the client_random that the client just sent, and none other (and similarly for the server).
The client and server "randoms" need not actually be random, although it is advisable. As explained above, the real value in the client and server random values is that they are distinct from previous values, for each handshake. They are public values, and there would not be any serious issue if they were predictable. Indeed, even if the attacker can predict the exact values of the client_random and/or server_random that will be used by given clients and servers, this won't help him running his replay attack: to succeed at replaying a handshake, the attacker must not simply know the client and server randoms; he must arrange for both client and server to reuse the same randoms as in the previous handshake which is replayed. Since the attacker impersonates only one at a time, he cannot enforce such reuse.
You may note that the said 32-byte randoms actually begin with 4 non-random bytes: these bytes encode the current date and time (number of seconds since a conventional instant). The purpose of these bytes is to try to ensure this non-reuse policy even for implementations with so terribly dysfunctional PRNG that they reuse previous random values. However, if the client has no good random source, this may have impacts on the security of the ClientKeyExchange and the master secret, especially with RSA-based key exchange (as is commonplace).
