I don't have any experience with this particular processor.

But It seems that the programmer can't switch the clock of the target 
because he is unable to communicate correctly.

Maybe there is a jumper on your board to set it slower and or you can 
try to set the communication speed in the command line (or gui option) 
of avr dude, or you can make an update of your usbasp's firmware as 
avrdude suggests.

As you can see you have plenty of options left ;-)

I cant update I would need a 2nd programmer for that :) the last update 
is from 2011 so Im reasonable sure this is the latest version.

With AVRDUDESS I tried all the -B options from 500Hz up to 1.5Mhz. Would 
I be correct to assume that this -B bit clock speed is the frequency the 
chip should operate based on the oscillator the board has? (in my case 
16mhz) or is this something different?

@nightowl

All articles I found on updating the programmer look like this
http://www.rogerclark.net/?p=702 using either another of the same type 
or other arduino to do it.

I just managed to push through all the errors and upload a bootloader, 
but now that I want to upload a sketch I get timeouts.

You are right. I thought if my programmer is capably of that all others 
could be too. That is unfortunately untrue. I took a look with google 
and came to the same conclusion. The 3rd option was to burn the atmega8 
with the usbasp and change it then with the programmer.

Have you checked if there is a wrong crystal or resonator on the board?
Are you able to read the fuses?
Could you post the error massage(s)?

The crytal is right, and I read that the chips are rated for max 20mhz 
and the fuse settings are the same.

In the mean time I managed to upload a bootloader/set fuses despite the 
error but the process is faulty because it always timeouts when I then 
try to upload firmware.

From where I stand now I can reasonably assume that its just the 
programmer. I'll visit a friend with an adrudino and I'll try the 
Arduino as ISP method.