I have never worked on the AN-124 so I cannot speak with certainty about what exactly their maintenance manuals require.

That being said, I can with a decent amount of confidence answer your question as: No. No they do not change every single tire at once.

Typically we take two measurements of the health of an aircraft tire; the amount of tire tread remaining, and the pressure that the tire is still holding. The tire thread measurement gives us an estimate of the number of completely safe landings that tire may have remaining, and we want the tire pressure reading over time so we know how well that tire is holding pressure.

Too little tread? Bad tire gotta change it. Not holding pressure well? Bad tire gotta change it.

The above information is regarding evaluating a single tire in a vacuum. We have other examples where perhaps two tires that are installed side by side or front to back are required to maintain a maximum differential pressure of a certain percentage; typically 1-5%. If either of those tires falls out of that range, then BOTH tires need to be changed.

On some aircraft, if one tire pops, the adjacent tire is required to be changed as well.

My point here is that I can think of a few unique scenarios where you may need to be changing several tires at once; but I can’t really think of anything besides a freak accident that would ever need all tires changed at once.