So, how does the CPU fetch a new instruction every cycle, if it takes more than one cycle to even fetch an instruction?
It could be done by starting the next fetch before the previous one completed.
An L1 hit may "take around 4 cycles", but the number that is thrown around a lot is the load-use latency of hitting the L1D cache and then using the result in an ALU operation (which isn't representative nor predictive of what goes on in the front-end of a processor), and it normally refers to architectures that have a significantly longer pipeline the one that the diagram in your question is for. If the diagram shows a single cycle FI stage, I'm inclined to believe it: that architecture probably fetches an instruction in a single cycle (which was, and still is, a normal thing for architectures that aren't "super-pipelined"), otherwise the diagram should show more fetch stages.
The kind of architecture which that "4 cycles" figure is about, look more like this (actually the load-use latency is only 3 cycles here, but you get the idea):
How long the I-cache access takes is not so clear from this diagram, but I argue that it should be at most 3 cycles and possibly less, because after 3 cycles there is an arrow going down to the decoders and by that time the instruction data should be available, otherwise there would be nothing to decode. But how long the cache access takes is not that important (well it is important, but it's not as bad as limiting fetches to on in k cycles where k is the cache latency), whether it takes 1 or 2 or 3 cycles, one access can happen every cycle, so when all goes well the pipeline can stay full.