just a late night idea:
since the Atmega8 is so cheap, why not put two or more on one board, write a slim but effective communication protocol and.. voilà... get a real multiprocessor machine.
This seems to be the perfect starting point: http://www.arduino.cc/en/Main/ArduinoBoardPrototyping