Patent free symmetric-only key exchange protocols?

Key exchange protocols break up into two major categories. Server-Based key Establishment and server-less key establishment (I think I'm going to buy that book.). Within these two categories you'll find protocols that use symmetric or asymmetric ciphers or both. There are lage number of Key exchange protocols documented on Security Protocol Open Repository(SPORE), which is a very cool resource.

A good choice for server-based key Establishment is the Needham-Schroeder Symmetric Protocol which can be performed entirely with AES and is used in Kerberos.

For server-less key establishment you should look at Lowe modified BAN concrete Andrew Secure RPC. It is old, however I do not believe this protocol has been compromised.

You should use SSL/TLS whenever possible, but it will require more than 1kb of memory.