A standard '51 with 12MHz clock - about 417, not counting the two- and three-cycle instrutions. Pretty safe margin if you do your programming in ASM.
Or what priority it is (you may always override lower-priority interrupts...)

If that's an external interrupt, the "standard baud rate matching" i.e. by using 11MHZ instead of 12 is not an issue (or issue of the external device). Over 400 cycles is quite a plenty, I guess the described task could be performed in some 8 instructions - taking maybe 2% of CPU time with standard '51.
Of course sloppy C code may slow it down drastically.

So, the answer to the original question should be - yes, unless you expect some very specific application, it can be done.

Note something curious: using whole bytes even if you're interested only in one bit is often faster than using single bits. I.e. you can do MOV @R0,P1, MOV #0,P1, MOV somebyte,P1 but not MOV mybit,P1.0, mov ACC.0,P.1 or such - you're usually stuck with sequences like (MOV C,ACC.0 ; MOV P1.0,C) and such - so depending on your particular application, if you care about speed and have whole ports unused, sometimes you may consider setting whole port instead of a single bit even if only one bit is attached and the remaining 7 contain junk. YMMV.