How can different points on a rigid body move with different speeds but also be relatively at rest?
Having a non-zero relative velocity is fine as long as the distance between the points isn't changing. This certainly holds for a rotating rigid body. As another example, take a ball on a string and rotate it in a horizontal circle. Is the ball moving relative to you? Yes. Is it moving towards or away from you? No.
Therefore this part
If they have a non-zero relative velocity, the distance between them would change over time.
is the invalid step. This is not necessarily true, and it isn't true for rigid bodies.
See Mike Stone's answer for a simple geometric "proof" of this.
EDIT- Instead of the scalar distance, let's talk about the position vector of a ball that I rotate using a string. If I also rotate my body along with it with the same angular velocity, I'd find the ball to be at rest in my point of view. If there was a relative velocity $\vec v$ , wouldn't the position vector of the ball change given by $\vec r(t+dt)=\vec r_0+\vec v\,\text dt$?
Yes, if you are rotating with the ball then you would observe the ball to be at rest. You will be in what is called a non-inertial frame of reference. It is non-inertial because it is rotating (accelerating). In this frame of reference you would see a constant position vector for the ball and a $0$ velocity vector.
If the velocity of point B relative to point A is always at right angles to the line AB joining them, then the distance does not change.
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.