all I can say is good luck. at 115kbaud, that's less than 9 microseconds per bit. at 1 microsecond per instruction cycle at 4MHz, you've got very little time to do anything between bits... not to mention you will have very poor timing resolution which may cause some headaches. You may wish to switch to a 20MHz crystal, which will give you 5 times the instruction cycles per bit, giving you a lot more room to work, and 5 times better resolution.
I am not trying to shoot your idea down, as I myself have never tried doing 115kbaud via software at 4MHz. perhaps someone who has attempted it can offer more help.