If 0 Kelvin means object particles at complete stop and >0K meaning particles moving at a certain speed, shouldn't infinite temperature be impossible, since no particle can move faster than the speed of light?
The temperature of a low-pressure non-relativistic gas is indeed related to the average speed of the atoms in a simple way. However, temperature, in the general case, is more closely related to the average energy of a particle (so the energy and temperature can both grow without bound as the speed approaches closer and closer to the speed of light). However, even that "definition" of temperature is rather imprecise.
There are many mathematically equivalent versions of the "complete" definition. My favorite is the zeroth law of thermodynamics: If body A and B have the same temperature (meaning there is no heat flow between them when they touch) and body B and C have the same temperature, then body A and C also have the same temperature. Basically, you define the words "thermal equilibrium" to mean "there is no heat flow when they touch" and you also define temperature to be the quantity that is equal in that case. This together with the "conservation of energy" and "growth of entropy" (basically the axioms of thermodynamics) is sufficient to derive most properties of temperature you know.
If you have already defined entropy in some other way, you can say "the temperature of an object tells you how much the entropy of the object rises for a unit rise in the internal heat energy of the object":
ΔEntropy = ΔEnergy / Temperature
If you have not yet defined entropy, but have defined temperature (which I personally see as easier to understand), then the above equation can be your definition of entropy.
Notice that "definition" just needs to be mathematically sound (i.e., self consistent). But for a physicist to want to use such definitions, they *also* need to be practical. Any of the (equivalent) definitions above are a fair choice, as they happen to be the self-consistent principles which do lead to behavior like the one we experimentally observe.
I do imagine that a rigorous mathematician might have a reason to prefer one of the aforementioned definitions more than the other. I do not have such concerns.
Lastly, concerning the gases: If you happen to know that gases are made out of moving atoms then you can do a bit more. Mind you, you can build most of thermodynamics without that knowledge. But if you know that fact, then you can derive that temperature is related to some measure of average energy per atom. If the atoms are relativistic, then energy per atom will need to be written in the relativistic form (which does not grow to infinity as velocity approaches the speed of light). At lower speeds, the formula for the energy becomes numerically indistinguishable from the one from classical mechanics.
Temperature is proportional to kinetic energy only in specific conditions. In its more general definition, temperature is how energy changes with entropy. You can have temperatures tending towards infinity, and even negative temperatures.
