The time it takes a moon to become tidally locked to a planet depends on a number of factors. In particular,
$$t_{\text{lock}}\propto\frac{\omega a^6}{m_p^{2}}$$
where $\omega$ is the moon's initial angular speed, $a$ is its semi-major axis, and $m_p$ is the mass of the planet. There's a very strong dependence on $a$ - double it, and we increase $t_{\text{lock}}$ by a factor of 64! So if it takes, say, 10 million years for a moon with semi-major axis $a_1$ to become tidally locked with its planet, then a moon with semi-major axis $a_2=2a_1$ could take 640 million years to become tidally locked - even if they started with the same period of rotation.
Let's crunch some numbers. The initial conditions of the Moon after its formation are unknown, but there's been some modeling of them. Cuk et al. (2016) did some simulations of the rotation of both Earth and the Moon. Using their modeling, I'm going to assume several things:
- The Moon's initial angular speed was $\sim10^{-5}$ radians/second.
- The initial semi-major axis was about 25 Earth radii, or $\sim1.6\times10^8$ meters.
- The time until tidal locking was about 20 million years, give or take.
Therefore, using the mass of the Earth, $M_{\oplus}$, we find that
$$t_{\text{lock}}\approx2\times10^7\left(\frac{\omega}{10^{-5}\text{ rad s}^{-1}}\right)\left(\frac{a}{1.5\times10^8\text{ m}}\right)^6\left(\frac{m_p}{M_{\oplus}}\right)^{-2}\text{ years}$$
This does assume that certain physical properties of the satellite, such as its radius, mass, and love number are all the same as the Moon's. However, it's simple to add more terms to the scaling relation to take this into account. Notice that if we take the ratio of the tidal locking timescales for two moons orbiting the same planet, the term involving $m_p$ drops out.
Now, this kind of variation is possible. The moons of Mars have significantly different orbits; Deimos has a semi-major axis two and a half times as large as Phobos'! We see even greater variation in the moons of giant planets, such as the moons of Saturn, but I doubt there would be that sort of orbital difference around terrestrial planets, for the simple reasons that 1) it's hard for lower-mass bodies to form many moons, and 2) the Hill sphere - the region in which an object can have satellites - is smaller for low-mass planets.
It seems likely - possible, at the least - that the moons around the giant planets formed at different times. Some of the ones with smaller orbits could have formed with the planet, out of the disk of dust and rock surrounding it. The outer moons might have been captured later on, from asteroids or bits of protoplanets. Additionally, some may have formed in collisional families, meaning that some groups of moons could have formed at different times. Each group would have formed from the fragmentation of an asteroid captured by the planet - the Ananke and Carme families of moons around Jupiter are prime examples. Of course, less-massive terrestrial planets are less likely to capture asteroids, but then again, the moons of Mars were likely once asteroids.
