Does helium freeze at absolute zero? In theory, it should, since all random motions of particles stops at absolute zero, right?
Not at atmospheric pressure. You need at least 25 atmospheres pressure to solidify helium-4 and at least 29 atmospheres (0.3 K) for helium-3. See Wikipedia.
At low pressure you fail to solidify the helium because of weak interatomic interactions combined with quantum mechanical zero point energy. Higher pressure favors forming a denser structure with an ordered lattice arrangement, thus a crystalline solid.