Why isn't everything massless if nothing is at rest? I've read the following statement a couple of times on my research on how Photons (or anything) can be massless:

Mass is the energy of a body at rest. Photons are never at rest.
  Mass is the non-kinetic energy of a free body. All a photon's energy is kinetic.

So isn't that a contradictory statement. Regarding to our knowledge about the universe, so far, nothing is ever at rest. The earth spins, the solars system is spinning, our galaxy is spinning, everything is moving towards the great attractor and the universe is expanding. So how can be anything be described as having a mass higher than 0?
 A: You should read it as "Mass is the energy of a body when measured in its rest frame". Mass doesn't disappear nor change when you switch to another reference frame where the body is in motion. It's just that the energy of the body no longer equals to its mass, when the body is in motion.
A: This is a misquoted statement of something like:

Mass is the energy of the particle in its rest frame.

It is a statement from special relativity where :
$$m_0^2c^2 = \left(\frac E c\right)^2 - \lVert\mathbf p\rVert^2$$
In natural units where $c=1$, this becomes
$$m_0^2 = E^2 - \lVert\mathbf p\rVert^2$$
When the momentum is zero , by definition the center of mass system of the particle, the mass and the energy are equal.
It is called the invariant mass, and it is the length of the four vector of energy momentum in the pseudoeuclidean space of special relativity .
This means that even two particles whose invariant mass each is zero, will have an invariant mass if their momentum vectors are not collinear.
A: The statements made are accurate, but putting them together does lead to some interesting  misconclusions that are easy to draw.
First off, I will assume we are talking about relativity and that we are comfortable with why we model the universe using relativity.  If we're not exploring relativity, the concepts you quoted stop being meaningful, so relativity it is!
Now relativity is all about different reference frames, what we have to agree on, and what we may differ on.  For sake of the story, let's assume that we are in different reference frames that are moving apart by a constant velocity.  From these frames, we measure the mass and velocity of an object (maybe it's an asteroid, or a star, maybe its your mass or mine.  Pick any object, it won't matter).  Obviously we will disagree on the velocity of the object.  Even without relativity it's obvious that we'll come up with different velocities, just like how a man on a train sees things moving at a different speed than a man on the ground.  However, the interesting part which relativity predicts is that we would measure the mass of the object as being different as well!  If we watched an interaction (such as a collision) we would disagree on how massive the object was.
However, if we compared notes and crunched some numbers, we would see that there is some value we can both agree on.  In particular if we took the sum $m+\frac{E}{c^2}$ we would find that we both agree on that number.  This is the conservation of mass-energy.  Any observer, in any frame, will find the same mass-energy value for that object.
Now what if you had an object that was holding still.  Well, obviously in such an environment, the kinetic energy is 0, so that sum just resolves to $m$ or the rest mass/invariant mass of the object.  This is an intrinsic property of an object which we can come to simply by making the reference frame follow the object wherever it goes.
To your point about "nothing is ever not moving," that is almost true.  However, for every object, there is at least one reference from where the object isn't moving.  Any measurements of mass in that frame will be "rest mass/invariant mass."  If you are not so privileged as to get to measure the mass of an object in such a frame, fear not!  If you trust that the equations from relativity hold, you can calculate the velocity of the object (in your reference frame), calculate the perceived mass of the object (in your reference frame), and do math to calculate the "rest mass" of the object (in a reference frame where its velocity is 0).  You can also trust that, if someone else (in a different frame) does the same set of observations and calculations, they will arrive at the same "rest mass" number, even though their observations may show a different perceived mass and velocity.
