Usando la propiedad arquimedeana tienes que para toda $\varepsilon>0$ existe una $n_1$ tal que $n_1 \varepsilon>x$. Tomando $\varepsilon=1$ y usando el principio del buen orden puedes encontrar la mínima $n_1$ tal que $x<n_1$. Como $n_1$ es mínima, eliges $n_0=n_1-1$ y ya acabaste. Supongo que esa es la demostración que ya tenías.
Otra opción es usar el principio del supremo (que creo que el Rudin toma como axioma). Como existen enteros menores que $x$ (por ejemplo, el 0), el conjunto de enteros menores que $x$ es no vacío. De nuevo, por la propiedad arquimedeana, existe algún entero mayor que $x$, por lo tanto el conjunto de enteros menores o iguales que $x$ es acotado. Sea $n_0$ el supremo de tal conjunto. Ahora tu problema es demostrar que $n_0$ es entero. Supón que no lo es y usa la densidad del orden de los reales para demostrar que hay una cota más chica.