Yeah, 8-bit timers are out for driving hobby servo PWM directly.. 16-bit timers work really well with the right prescaler. Several of the lower end AVRs have one 16-bit timer with usually 2 Output Compares, so you can drive two servos. The Atmega128 has two 16-bit timers with 3 output compares each. Of course Atmel sells a huge variety of AVRs, I need not mention the capablities of all of them.
The atmega 128 does have 8 external interrupts, they are split between ports D and E. I'm not sure if all 8 have exactly the same capabilities or not.
I've tried a variety of methods for /generating/ servo PWM, and hardware (Output Compare on Timer) is definately best if you can use it. I've run PWM via software as you describe, but it can be a huge PITA because you can get visible jitter if the timing varies by as little as a microsecond. Worse, if you're starting the pulses for several servos at the same time, getting all the pulses to stop at the correct time can be problematic in situations where, say, the servos are set to values close to each other. Imagine one servo being set 1us different than the next one. It can probably be done (some hand rolled assembly interrupt routines with a fast enough crystal, maybe), but what a pain.... And it limits what you can do elsewhere (I dont recommend trying to mix interrupt driven software I/O of some other type)
In my case I was trying to drive 3 servos with software using an Atmega32 (that was doing several other things too), at some point I got tired of fighting with it and went with a 128 so I could do up to 6 with hardware. Much simpler, no more timing issues, no more jitter.
Wow, this has really strayed off topic... Is the original poster still around? Did he get anything out of all this?