If the Roku device is new, or has been Factory Reset, then you need a remote to set the device up. If the Roku device is a Streaming Stick, will need a Roku Remote (ie. Roku Voice Remote). If any other Roku device, then an inexpensive IR universal streaming remote (compatible with Roku) can be used to setup and use with your Roku.
You are correct... the Roku has to have been successfully setup on a network before you can use the mobile Remote app.
If you have previously had it connected to another network and you know the other network credentials (SSID network name and password), then there are a couple of different methods to connect to the new network without a physical remote.