Trading on Mt. Gox, which is now the largest Bitcoin exchange, started in July 2010 at an exchange rate of $0.05 USD. This comment suggests that on May 2010, bitcoins were traded at bitcoinmarket.com for roughly $0.004 USD.
What other exchanges existed this early in Bitcoin's life? What is the earliest/lowest recorded exchange rate?