One possible solution is to buy an ATmega168 which has twice as much program memory as the ATmega8 (16 KB instead of 8). We've had a hard time finding them in Italy, but you might have better luck. You'll need to burn the bootloader on them, which will require an AVR-ISP or parallel port programmer. It might also require a bit of tweaking to the preferences file, but nothing major, I think.
Alternatively, if you reburn the bootloader with the "Tools | burn bootloader" menu command in Arduino, you should get an extra kilobyte of program space (7KB instead of 6).