[snarfy]

I believe you are referring to velocity = distance/time. This is the non-relativistic view of velocity. It makes more sense when you define what distance is.

When you push something with your finger and move it, you do not change it's velocity. You change it's acceleration. It's a small but important distinction. Under relativity, the distance between two points in spacetime is defined by the minkowski metric:

    d = sqrt( x^2 + y^2 + z^2 - (ct)^2 )

Notice time is negative/imaginary. The tl;dr of this is that an object at rest is still has a velocity along the time plane at the speed c, and any non rest velocity is relative to that (which affects d), which is where length contraction comes from. You're right in you can't define one without the other, so it's redefined around the constant c and the minkowski metric. It's why they call it spacetime.