It seems the sticking point is your notion that non-zero relative velocity implies changing distance. To see that this is not the case, consider a car. When you turn in a car, the outer tire moves faster with respect to the road than the inner tire, i.e. the two tires have non-zero relative velocities. Yet, the car does not fall apart.
The reason is that the relative velocity of the tires is perpendicular to the separation vector.
To prove this, let $\vec{r}_{AB} \equiv \vec{r}_B - \vec{r}_A$ be the separation vector from object A to object B. We compute
\begin{align}
\frac{d}{dt} ||\vec{r}_{AB} ||
&= \frac{d}{dt} \sqrt{\vec{r}_{AB} \cdot \vec{r}_{AB}}
= \frac{1}{2\sqrt{\vec{r}_{AB}\cdot\vec{r}_{AB}}} (2 \dot{\vec{r}}_{AB} \cdot \vec{r}_{AB}) = \frac{\dot{\vec{r}}_{AB} \cdot \vec{r}_{AB}}{||\vec{r}_{AB}||}
\end{align}
From which it follows
$$
\frac{d}{dt} ||\vec{r}_{AB}|| = 0 \iff \dot{\vec{r}}_{AB} \cdot \vec{r}_{AB} = 0
$$
Which is to say that two objects with a fixed distance can have a relative velocity. In fact, this is possible precisely when the relative velocity is orthogonal to the separation vector.
To see that the relative velocity really is perpendicular to the separation vector in a rigid body, note that in a rigid body (in a frame comoving with the center of mass) $\dot{\vec{r}}_A = \omega \times \vec{r}_A$ and $\dot{\vec{r}}_B = \omega \times \vec{r}_B$. Thus
$$
\dot{\vec{r}}_{AB} = \dot{\vec{r}}_B - \dot{\vec{r}}_A = \omega \times \vec{r}_{B} - \omega \times \vec{r}_{A} = \omega \times (\vec{r}_{B} - \vec{r}_{A}) = \omega \times \vec{r}_{AB}
$$
so
$$
\dot{\vec{r}}_{AB} \cdot \vec{r}_{AB} = (\omega \times \vec{r}_{AB}) \cdot \vec{r}_{AB} = 0
$$
To summarize: 1) It is possible for two objects with a fixed distance to have a relative velocity; they need only to have a relative velocity perpendicular to their separation vector. 2) Points on a rigid body move with a relative velocity that is perpendicular to their separation vector.
