Efficient setup for a Montgomery multiplication
The usual way is to calculate $2^k R \bmod N$ for a small divisor $k$ of $l$ where $R = 2^l$ and use Montgomery multiplication in a Square-and-Multiply algorithm. This does require a division, but as $R$ is usually chosen to be just a little bit longer than $N$, the division doesn't have to be optimized much.

But you should also consider the fact that in some occasions (like RSA key generation) one can do also without knowing $R^2 \bmod N$. You neither have to Montgomery transform the random bases for a Fermat or Miller-Rabin test nor a number you want to invert using Fermat's little theorem (in the second case just Montgomery multiply with $1$ afterwards).