$\mathbb{Z}[\sqrt{2}]$ is such a ring.
First, let us recall a simple algorithm that suffices to give a smaller remainder in this ring:
If $a,b,c,d \in \mathbb{Z}$, then $\frac{a+b\sqrt{2}}{c+d\sqrt{2}} \in \mathbb{Q}(\sqrt{2})$. Write $\frac{a+b\sqrt{2}}{c+d\sqrt{2}} = (n_{1}+r_{1}) + (n_{2}+r_{2})\sqrt{2}$, where $n_{1}, n_{2} \in \mathbb{Z}$, $r_{1}, r_{2} \in \mathbb{Q}$, and $|r_{1}|, |r_{2}| \leq \frac{1}{2}$. Then $|r_{1}^{2}-2r_{2}^{2}| \leq |r_{1}|^{2} + 2|r_{2}|^{2} \leq \frac{3}{4}$, so it is always possible to divide in $\mathbb{Z}(\sqrt{2})$ and get a remainder whose norm is at most $\frac{3}{4}$ times the norm of the element you divided by.
Then such a bound for the number of divisions (starting with dividing $u$ by $v$) is given by $\frac{\log_{2} |N(v)|}{2-\log_{2}3}$, where $N$ denotes the $\mathbb{Z}[\sqrt{2}]$ norm. If you want a bound in terms of another norm, it's probably not hard to relate it to this bound.