The TMS1000, which as far as I know has greatly more capability than the 4004 (I know the TMS1000 pretty well, but don't know too much about the 4004), predates the 4004.
I think Fairchild had something earlier, and it seems to me that Uncle Sam beat them all to it.
The 4004 is only very influential in retrospect, I think. It's only significant due to the current popularity of Intel. Had Intel not existed, I have no doubt that things wouldn't have been much different, progressively speaking. The early hobbyist machines may not have been 8008 based, they may have been bit-slice at first, and then Texas Instruments, General Instrument, Fairchild, Motorola, RCA, or someone else's microprocessor would have been used. I think the 6502 happens either way: it was intended for microcontroller applications, which would have progressed without microcomputers. A microcontroller or the like would end up in microcomputers, and clearly the 6502 advanced the state of the art in microcomputers quicker than the competition, anyway.
Don't get me wrong, I think it's important to preserve the history of the 4004. But no one is preserving all the others, and 4004 is getting undue credit. The TMS1000 may be the Multics of microprocessors.