If you have a signal
$$f[n]=\cos(\Omega_0n)$$
and you apply a time shift of $n_0$ you get
$$f[n+n_0]=\cos(\Omega_0(n+n_0))=\cos(\Omega_0n+\Omega_0n_0)=\cos(\Omega_0n+\phi)$$
where $\phi=\Omega_0n_0$ is the phase shift.
The other way around, if you have a phase shift of $\phi$, this is not always equivalent to a time shift of the original signal:
$$g[n]=\cos(\Omega_0n+\phi)=\cos(\Omega_0(n+\phi/\Omega_0))$$
which only corresponds to an integer time shift if $\phi/\Omega_0$ is integer, i.e. if $\phi/\Omega_0=n_0$ which results in
$$g[n]=f[n+n_0]$$
EDIT:
Re-reading your question, I think that the misunderstanding lies in the fact that you believe that the phase of a discrete-time signal must be integer. This is not the case. Imagine two continuous-time signals
$$x(t)=\cos(\omega_0t)\quad\textrm{and}\quad y(t)=\cos(\omega_0t+\phi),\quad\phi\in\mathbb{R}$$
Note that the following holds for any value of $\phi$:
$$y(t)=x(t+\phi/\omega_0)$$
So we can always express $y(t)$ as a shifted version of $x(t)$. Now imagine that we construct two discrete-time signals by sampling $x(t)$ and $y(t)$ at times $t_n=nT$ with some real-valued $T>0$:
$$f[n]=x(nT)=\cos(\omega_0nT)=\cos(\Omega_0n)\\
g[n]=y(nT)=\cos(\omega_0nT+\phi)=\cos(\Omega_0n+\phi)
$$
with $\Omega_0=\omega_0T$. Note that the phase $\phi$ is of course the same as before (and for this reason not necessarily integer). The difference between the continuous-time and the discrete-time case is now that $g[n]$ cannot in general be obtained from $f[n]$ by time-shifting because we can only shift by integers. The condition under which $g[n]$ can be obtained by shifting $f[n]$ is if $\phi/\Omega_0$ is integer because then we can write
$$g[n]=\cos(\Omega_0(n+\phi/\Omega_0))=f[n+\phi/\Omega_0]=f[n+n_0],\quad n_0\in\mathbb{Z}$$
