You are totally correct! Yes, velocity is relative, and therefore "relativistic mass" $m = \gamma ~m_0$ is relative: different people see different values.
However, here's the crucial part, anyone who sees you travelling at speed $v$ with mass $m$ agrees on this number $m_0 = m / \gamma$. It is what's called a "Lorentz scalar": every coordinate system agrees on this number, even though they disagree on $m$ and $v$ (hence $\gamma$). [Here $m$ might be defined best as "the ratio of observed momentum to observed velocity $v$."]
Special relativity has a lot of these numbers which everyone agrees on! In fact, if a photon is travelling past you at the speed of light, every coordinate system agrees on the speed of the photon. This is the basic thing that makes relativity special, and more strange to our ears than Newtonian mechanics.
In fact if you add the rest-mass-energy to the kinetic energy in relativity, you get an $E$ such that everyone agrees on $E^2 - p^2 c^2 = m_0^2 c^4$. The right hand side is stuff that everyone agrees on, therefore the left hand side must be, too! Taking the case where $p=0$ is where most people come to this statement that $E = m_0~c^2$, which is partly true -- it's true if the particle is at rest. In a more general case we would say $E = \gamma~m_0~c^2,$ and this indeed depends on how fast someone sees you going, getting larger as you go faster.
So, the easiest way to determine rest mass is to measure mass in a frame in which the object you're measuring is at rest: either with a scale in a known/constant gravitational field, or else by kicking it with a controlled impulse and seeing how it speeds up or slows down. But if you cannot do this, you can always measure its mass in the moving frame (again, kick it with a common impulse and see how much it speeds up / slows down; weighing it would be tricky) and multiply by $\gamma^{-1} = \sqrt{1 - (v/c)^2}$ to get the rest mass $m_0$. Or, you could measure its kinetic energy and divide by $(\gamma - 1) c^2.$ Any of these ways will tell you this constant about the particle which everyone agrees upon.