Clock recovery without a PLL relies on the assumption that there will be periodic edges in the data stream which can be used to resyncronize a drifting clock. No need for a PLL, nobody ever said that one was necessary. What is necessary is to know how the data stream is encoded so you know the maximum time between edges. This will put a bound on the amount of drift that you can tolerate.
If your little friends are telling you that you need one, you might want to consider getting some new little friends.
I mentioned USB as an example of a serial coomunication protocol that uses NRZI and bit stuffing. Controller Area Network (CAN) is another baseband protocol that uses bit stuffing, a programmable sample point, and maximum cable distance to allow syncronization of transmitter and receiver.
Even the lowly UART manages to maintain syncronization from the leading edge of the start bit over a 10 or 11 bit frame.
It is unfortunate that you've been assigned a task for which you are long on ambition, but short on support.