Microcontroller support for Teletype
If you have sufficient intercharacter space (~3 extra stop bits), you could use the MCU UART port, as there isn't really a difference between an 8-bit character (0x00 through 0x1F) on a UART and a 5-bit character with 4 stop bits.

Barring that, your best bet would be to use a level interrupt (pin change, etc) to detect the leading edge of the start bit, then configure a timer to interrupt you either once per bit or possibly a couple times so you can do some extra verification.  45 baud is really slow, so unless you're using upwards of 95% of the MCU time (or all it's peripherals), this shouldn't cause any problems.

The Atmel AVR USART module supports 5-9 bit modes, so any (newer) ATtiny (e.g. ATtiny2313) or ATmega (e.g. ATmega328P) will allow you to do this in hardware, vastly simplifying your software, saving your time.

The maximum clock divider you can apply to the UART on an AVR is 216, so if you have a clock of 16 MHz, the lowest rate it can run at is 244 bps with no system clock divider.  If you use an ATmega, like on an Arduino, the clock prescale register (CLKPR, §8.12.2 in Atmega48/88/168/328 datasheet) can be used to slow down the system clock up to 256x at run-time, or simply program the CKDIV8 fuse to set the prescale register's default to 8.

The real determining factor on what you should use is what else you're doing besides talking with the TTY.  If you are going to plug this into a computer, you will want to reserve a (or the, if there's only 1) UART for communicating with the PC and do a software UART if required (as mentioned by everyone, this is near trivial at 45 bps).  If you want to press a button and have the TTY do something, using the only UART for that would be fine.