In this situation, I will approach a speed of 0. Therefore, I will achieve a situation were the time between 2 pulses will theoretically be infinite. Why it is not possible to measure a speed of 0.

You dont need to measure 0 mph. All that's needed is a timeout that occurs at (for example) 0.005 mph, so anything within ±0.005 mph reads 0.00. Now your readings could sequence -0.02, -0.01, 0.00, 0.01, 0.02, etc mph.

The required precision for speed measurement is : 0.01 mph

For this example, lets use an encoder that's only 1 PPR

The wheel attached to it has a diameter of 12 inches.

The diameter here is 3.14 feet.

0.01 mph = 0.01467 feet/sec

Seconds/revolution(1 pulse) = 3.14/0.01467 = 214.15 seconds

Your timeout for measurement with ±0.005 mph could be 428.3 seconds, 428300000 µs

The function micros() overflows approximately every 70 minutes (no problem here).

What is the minimum update interval for speed : I don't know how to obtain that (I am not sure to understand what information you want)

If you need to see the speed (mph) update its reading every second at the slowest speed ±0.01 mph, then you'll need an encoder that has at least 214 PPR rating. Higher is OK, but I don't think you need 40,000 PPR