Atmega8 with Arduino bootloader - wrong serial characters
Ok I found a solution (rather workaround).

I uploaded the same program to Arduino Uno. It worked perfectly. I transplanted the Atmega328 from Uno to breadboard. Still worked BUT the Atmega328 is using external 16Mhz crystal (which I added to the breadboard).

So what if I uploaded bootloader for 16Mhz external crystal on Atmega8?
It makes it work properly.

So in short:
Atmega8 with 8Mhz internal oscillator doesn't work properly.
Atmega8 with 16Mhz external oscillator works properly.

Don't know why does it make it work. If anyone can think of a reason I would be glad to know it. Thanks for all your help.