Hmm, SEROUT2 (ie software UART) may not be a good idea. The interrupts will screw with the timing. The PIC12F1822 looked perfect for this untill I saw it was listed as a future product... (It's an 8-pin device with USART and Interrupt on change feature). Maby you can use it for the production model ;-)

The PIC16F688, though a 14pin device, is available and has both USART and interrupt on change feature (on 6 pins), have a look at that.