Sample synch. signal with unknown phase shift

Some points are unclear in your specification. What's the data rate and respective skew tolerance?

What causes the "maximum 3 clock cycles latency" requirement? You have a cable delay of more than 1 us and can't accept another 100 ns?

If the data rate is 40 MHz, oversampling with a factor of 4 or 8 should be sufficient to correctly align the input data.

Altera FPGAs have powerful features for skew adjustment of high speed serial interfaces. But they are not available for the large number of inputs.

Generally I wonder, if a data serialization and a fast, preferably optical medium would allow a simpler design.