How to implement line code?
The bad news is: Some problems are simply unfixable in software; you must either relax your constraints or else add new hardware.

Many optical coupling systems have turn-on delays not exactly equal to turn-off-delays, as you already noticed: "..00100.. the 1 appears longer ... ..11011.. the 0 appears shorter.".
In this system, the 1-to-0 delay is longer than the 0-to-1 delay.
If you are lucky, those delays are consistent enough to be compensated for.
A pulse stretcher can be as simple as a diode, a capacitor, and a couple of resistors.

Many line codes seem to meet your criteria, including
4B5B coding,
8b/10b encoding (or either one of the 3b/4b or 5b/6b codes typically used in it),
6b/8b encoding,
Manchester coding and its variants such as Differential Manchester encoding,
Three of Six, Fiber Optical,
Pulse-position modulation,
etc.

software compensation

I'm guessing you already have some free-space optical communication hardware set up that is a little quirky, and you're trying to compensate for hardware quirks entirely in software.

One quick-and-dirty scheme is:


Send a preamble just before sending each packet of data, typicaly a "balanced" pattern, perhaps 'U' characters (binary 0101_0101), to help the bit-slicer in the receive hardware find the appropriate setpoint to distinguish between 0 and 1.
Send bytes (perhaps using the UART or the SPI peripheral in the sender) from a short list that are "easily discriminated" at the receiver. I've seen some systems that send only two unique bytes out a UART configured as 8N1 -- 0x00 (i.e., 9 zero bits followed by 1 one bit) and 0xFF (i.e., 1 zero bit followed by 9 one bits). (They have only 2 bytes in that list). If you are lucky, you can use a larger list.
The receiver, for each byte received (perhaps using the UART peripheral), use a lookup table to decode it into the appropriate bits. With the above example, the receiver decodes "short" pulses of zeros as a 1 bit, and "long" pulses of zeros as a 0 bit.


Many line codes can be adequately approximated by dividing bytes up into a sequence of hexadecimal digits (nybbles), quaternary digits, or individual binary digits (bits), and then designing a lookup table that transforms that digit into 8 or 10 or 16 or so bits (chips) that, when sent out the UART or the SPI peripheral, adequately approximates that line code.

Perhaps your system can reliably distinguish between 16 different transmitted bytes, so each transmitted byte transmitted can be decoded into 4 data bits -- your transmitter uses one of 16 bytes in its short list. When you send a byte with an isolated 1 bit, and the hardware stretches it enough that the receiver sometimes sees a pattern with a single 1 bit and other times sees a pattern with two 1 bits, both of those patterns must be decoded into the same 4 data bits. (Also, the receiver must somehow throw away any between-packet noise, throw away the 'U' preamble bits, etc.).

pre-emphasis

Sometimes you can insert a pulse stretcher somewhere in the transmitter hardware, and tune the resistors in the transmitter such that, at the critical point in the receiver, the 1-to-0 delay is practically the same as the 0-to-1 delay.

post-emphasis

Sometimes you can insert a pulse stretcher somewhere in the receiver hardware, and tune the resistors in the receiver such that, at the critical point in the receiver, the 1-to-0 delay is practically the same as the 0-to-1 delay.

Existing implementations

There are several existing implementations of free-space optical communication that run at 1 megabit/second or faster.


Infrared Data Association (IrDA); if you are lucky your microcontroller already has some hardware support for IrDA)


MIR at 1 Mbit/s (?)
FIR at 4 megabit/second (Searching http://Digikey.com/ for "irda fir", without quotes, turns up a bunch of transciever modules. Perhaps "Can IrDA FIR module (A) be directly connected to the SPI or UART pins of microcontroller (B)?" would make a good independent question?)(Would any of the circuit diagrams in the LT1328 datasheet work for you?).
VFIR at 16 Mbit/s

RONJA (10 megabit/s full duplex)
Li-Fi ("1.6 Gbit/s" ?)


Would one of those work for you?