3000 x per minute x 4 fans = 200 per second.
Assume you catch only one edge, all you have to do is configure interrupts for one edge on the connected pin, and increment a counter for that fan each time. If you go over 15 sec periods, then you can left shift the result twice (x 4), and you will have 4 RPM updates per fan per minute.
Each 15 seconds, you take the current count, multiply by 4 and store as current RPM for that channel. Zero the counter, and repeat the procedure for the next fan.
200 interrupts per second is nothing for microcontrollers these days. Not for such a simple task, anyway.