I might start with an arduino and maybe some bitbanging on the aldl port and leave the uart port for debugging w/a laptop. The obduino code has some 300 baud bitbanging (at least for output) in it, fyi.
found a little data here on the aldl protocol:
Information on GM's 160 baud ALDL data stream
160 baud is slow enough that a firmware only solution sounds very possible.