Also consider that there are faster drop-in replacement like the atmega328 (cost < $3)
The atmega328 isn't actually faster, it just has more memory. Also, it might be worth looking at one of the cheaper low-end ARM microcontrollers with integrated USB; they have a lot more processing power and aren't much more expensive.
Hmm, no. ATmega8 runs at 16MHz while the ATmega328 can run at 20MHz, so it's roughly 25% faster.
Also, one very important warning: do not screw up and use a weak random number source. Your users will never forgive you.
IIUC the project I linked above is using a capacitor connected to one of the ADC as a source of randomness. It might not be as good as one of those TRNGs, but with some decent entropy estimation, followed by equalization and whitening it should make a decent entropy source.