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.