Logically, the console would be accessible there. I salvaged a flat cable with a connector from my Rio Karma dock and stripped extra conductors to bring the pin count down to 20. Next I needed a TTL-RS232 converter. I almost bought one from EBay, but then realized that I already have one in the form of a data cable for my Samsung GSM phone. I stripped the phone connector, spent some time to discover the pinout of the cable, and was ready to search for the console. With a multimeter I found grounded pins of the debug connector so I knew which ones I can skip. I then started PuTTY, set port parameters to 115200/8n1 (gleaned from source code), connected ground of the cable to the shield, and started connecting RX of the cable to every pin in order, resetting the Kindle each time. Eventually I was able to see the output of the bootloader.
check_recovery: shift-<r>ecover, shift-<u>pdate, shift-</> reset...
U-Boot 1.1.2 (Oct 29 2007 - 16:35:25)
*** Welcome to Kindle ***
With a bit of solder I fixed it, and then did the same with the TX wire while pressing some keys on the keyboard. As I was at the login prompt at this point, once I had the correct pin I could see the echo in the terminal. Unsurprisingly, the RX pin was right next to the TX.
I wasn't able to solder cable to the connector without shorting (the pins are 0.5mm apart!), so in the end I removed most of the pins, soldered short wires to the removed pins and inserted those I needed back into the connector.
The final pinout:
12 TX (connect PC's RX here)
11 RX (connect PC's TX here)
10 GND (also 7 and 3)
There are probably JTAG pins too, but those are a bit harder to find by trial and error. Also, I don't have a JTAG cable.
In case you want to make your own connector, you'll need:
1) a 20-pin 0.5mm pitch flat flex cable with a connector. Digikey seems to have some.
2) a TTL-RS232 or TTL-USB converter. For the former, make sure you get one that can handle 3.3V levels (i.e. MAX232 analog won't do, you'll need MAX3232 or similar). For the latter, probably any will do.