What is an efficient way to divide clock by 1000 or more?
If you want to implement a circuit like what you describe using off-the-shelf chips, I would estimate that it would take three decade counter chips (two of which will be used for divide-by-five, and one for divide-by-four), two 74HC595 chips (shift register with latch), one 74HC374 (8-bit latch), a segment driver chip, some transistors and resistors to drive five LED-digit commons, and probably about 3-4 miscellaneous "glue logic" chips (quad NAND, quad XOR, etc.)

The basic circuit looks something like this; as illustrated, it would run off 20Khz rather than 100Khz, but a decade counter wired as divide-by-five would easily fix that.

The LEDs flash digits in the order 1000ths 100ths 10ths units tens.  Although in this schematic I use a 20-bit latch with outputs fed back to inputs, it would be easier to use a shift register chip for 16 of the bits.  The shift register chip (74HC595) would also offer the benefit of including a free output latch (equivalent to the one in the lower right).

If one were to omit the "AND" and "OR" gate near the top-right of the schematic, it would count in binary.  Each bit is the xor of itself and the previous carry, and the new carry should be the "and" of the previous carry and the previous bit, except that on the first bit each "frame" the carry should be forced on.  Very simple logic which allows for any length increment to be performed by a shift register.  A slight 'wrinkle' in this variation is that the circuit will latch every four bits (since every four bits will need to be displayed as a decimal digit) and also test whether a latched digit is 9 and a carry is set; in that case, it will "pretend" that the next four bits from the shifter are all 1's, meaning that that digit will wrap to zero and the carry will be live for the next digit.

If one didn't need to display the count values, it might be simpler to just cascade one divide-by-ten counter for each digit.  On the other hand, this circuit offers the advantage of being able to multiplex five digits on a single display driver.  If desired, it could easily be adapted to handle any number of digits, simply by adding more shift registers and adjusting the timing circuitry.