You could use programmable logic as single chip solution. CPLD (Or older GAL, PAL...)
You could use a microcontroller as single chip solution.
You could use two HC390.
You coud use ICM7217 as 4 digit decimal counter with multiplexed BCD outputs (+ 7 segment LED display controller)
One other off beat solution might be an MC145151-2.
This contains a crystal oscillator and a 14 stage divide by N counter.
The counter division can be set to any number between 3 and 16,384 with fourteen programming pins.
It can certainly divide by 10,000 (or just as easily 10,001 or 9,999)