You shouldn't need to get an external clock at all. 8 MHz internal should be fine.
If it has same problem with 8 MHz internal, the next thing I'd do is try to figure out whether the problem is in writing to the tm1637 or reading the temperature from the MLX, by just writing sequential numbers to the display so you could see if it was sometimes displaying garbage even without reading from the temperature sensor.
The accuracy of all the internal clock options is the same (1 MHz is generated from the 8 MHz one through a /8 prescaler, and the 16 MHz PLL option available on t85 and t861 (requires 4.5V+) is also generated from the same 8 MHz internal oscillator (multiplied by 8 and then divided by 4).
Internal is typically within 1-3% on classic AVR parts at room temperature and 3-5V (the datasheet specifies +/- 10% but in real-world conditions, it's much more accurate than that; I don't think I've ever seen one that wasn't within 4% at room temp and normal voltages), and neither of those parts requires exact clock speeds (they're both I2C-like interfaces, not weird timing-critical ones).