Если скорость UART будет 115200 - то всё успеете. Прерывания на мегагерцы, по-моему, не нужны (да и не успеет процессор

) Для проверки длительности битов по-моему достаточно будет таймера, запускаемого при приёме очередного бита (ну это при условии что от Вашей схемы на TTL придут уже готовые сигналы битов 0 и 1, а это видно так и есть, раз Вы собираетесь использовать всего два входа, а не три). Прерывания от INT0, INT1, приёмника и передатчика UART, переполнение от таймера - мне кажется этого будет достаточно. Если сомневаетесь, можно применить мегу из новых серий, которые работают штатно до 20 МГц.
А, да, передача - на неё ещё один таймер. Так как +- 5% то беспокоится по поводу "сбивания времянок" прерываниями наверно не стоит...