if mass is dependent on velocity, and velocity is relative, how can we determine rest mass If I'm not mistaken, $m=\gamma*m_0$ ($\gamma$ being the lorentz transformation)
But $\gamma$ depends on velocity. How do we determine velocity if velocity is relative? If we are currently being flung through the universe at vast speeds, and there's no absolute grid system to compare this to, then how do we know what our true velocity is? Do we know how fast we are moving through the universe, and as an extension what percentage of the speed of light we are going? Furthermore, if there is no absolute grid system, then if we are moving towards a galaxy, then would our speed and therefore mass be greater than if we moved away from said galaxy? As an extension, how do we know what our rest mass is? When people say the rest mass of an electron 9.1*10^(-31)kg, is that when it resting relative to the earth? If so, would this change if the earth was to speed up?
 A: 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.
A: The value of velocity depends on the observer.  Therefore the value of $\gamma$ depends on the observer.  Therefore (since the value of $m_0$ does not depend on the observer) the value of $m=\gamma m_0$ depends on the observer.
It's not entirely clear what's confusing you, but you appear to be assuming that  $m$ should be observer-independent.  It's not.
So if you measure $m$ for a given particle while moving away from it at one velocity $v$, and then measure it again while moving away from it at a different velocity $v'$, you will indeed get different values.
It's not clear why you believe this is a problem for determining rest mass.  You appear to believe that we can only measure $m$ directly and to be unsure how we could measure the rest mass $m_0$ directly.  Answer:  $m_0$ is equal to the value of $m$ measured by an observer at rest with respect to the particle.  So if $m$ is measurable, then so is $m_0$.
A: When the particle is stationary in your frame, the mass you observe is the rest mass.
A: As the definition of "rest mass", when the item is relatively static in your frame, the mass you observed is the rest mass.
