Parallel-In-Serial-Out with Parity?
I would clock the byte into a Parity Generator, then clock the output of that into a 9 bit Parallel-In-Serial-Out shift register, and shift away...

Sure, it's two chips, but it's better than a programmable part.

74HC280 and 
SY10E142 

Or equivalents.