Solution:
The possible sets are $\{0,1\},\{0,1,2\},\{0,1,2,3\}$ and $\mathbb{Z}_{\geq 0}$.
Since $d$ is defined as a distance, we also have the triangle inequality, stating that
$$d(x, y) \leq d(x, z)+d(z, y)$$
for all $x, y, z \in \mathbb{Z}$. Now note that for all $x \in \mathbb{Z}$ we must have $d(x, x+1) \mid 1$ and thus $d(x, x+1)=1$. Iterating this result with the triangle inequality we find that $d(x, y) \leq |x-y|$ for all $x, y \in \mathbb{Z}$. If we consider the graph on $\mathbb{Z}$ where $x, y$ are connected if and only if $|x-y|=1$, then we have $d(x, y)=|x-y|$ which satisfies the condition. Excluding this case, we can assume without loss of generality that $d(0, a)<a$ for some positive integer $a$, after shifting $d$ accordingly. Moreover, we can assume that $a$ is the smallest positive integer with this property. If $d(0, a)<a-2$, then we would have
$$d(0, a-1) \leq d(0, a)+d(a, a-1)<(a-2)+1<a-1$$
contradicting minimality of $a$. Hence, $a-2 \leq d(0, a)<a$. But we must also have $d(0, a) \mid a$, which together with $d(0, a)<a$ implies that $2 \cdot d(0, a) \leq a$. Putting the two inequalities together we find that $2(a-2) \leq 2 \cdot d(0, a) \leq a$, which is equivalent to $a \leq 4$. In particular, we have
$$d(0,5) \leq d(0, a)+d(a, 5)<a+(5-a)=5$$
and hence $d(0,5)=1$. Since for all integers $k$ we have
$$d(k+1, k+6) \leq d(k+1, k)+d(k, k+5)+d(k+5, k+6)=d(k, k+5)+2$$
and similarly $d(k, k+5) \leq d(k+1, k+6)+2$, it follows that $d(k, k+5)=1$ for all $k \in \mathbb{Z}$. Now note that for all $k, t$ we have
$$d(k, t+6) \leq d(k, t)+d(t, t+5)+d(t+5, t+6)=d(k, t)+2$$
and similarly $d(k, t) \leq d(k, t+6)+2$. It follows by induction that $d(k, k+6 t \pm 1)=1$, where the base case $t=0$ is trivial and we use the fact that $6 t \pm 1$ is coprime to 2 and 3. Now since each integer is at most distance 2 from an integer of the form $6 t \pm 1$, it follows that $d(x, y) \leq 3$ for all $x, y \in \mathbb{Z}$.
Now set $S=\{d(x, y) \mid x, y \in \mathbb{Z}\}$ and note that certainly $0,1 \in S$. If $3 \in S$, then we must also have $2 \in S$ since any shortest path of length 3 can be shortened to a shortest path of length 2. The only remaining possibilities for $S$ are
$$\{0,1\}, \quad\{0,1,2\} \quad \text{and} \quad\{0,1,2,3\}$$
Now consider the graph where $x$ and $y$ are connected if and only if
$$x-y \equiv \pm 1 \quad(\bmod 6)$$
and a quick check shows that this graph satisfies the condition and $S=\{0,1,2,3\}$. Considering instead the graph where $x$ and $y$ are connected if they are of different parity, we also check that the condition is met and $S=\{0,1,2\}$. Finally considering the complete graph on $\mathbb{Z}$ also shows that $S=\{0,1\}$ is possible.