You'll probably want to multiplex the display to minimize the amount of wiring and Arduino pin usage (although you could just do a long string of shift registers in series, since you don't need to update the display very often for a clock).
My suggestion: go shopping for driver chips first, then build the display for the one(s) you like. Years ago, common cathode was more popular, but common anode seems to be more so now.
I have some MC14489s left over from a long-ago project, which are nice SPI-based 5-digit common cathode drivers that I think are still available cheap. I just picked up an SAA1064 that I haven't tried out yet. It's I2C, common anode, that only muxes 2 digits, so I'm hoping it'll be brighter than chips that multiplex several digits.
Somebody posted about the AS1106 a few days ago. It looks like a nice inexpensive 8-digit common-cathode driver, but I haven't tried one out yet.
Ran