TL;DR: To setup a Fire TV stick without a remote, you need: A USB OTG cable. A keyboard. The Fire TV app.

Recently, I bought a used Amazon Fire TV stick online, that featured a "little surprise": its remote control was broken. At first, this rendered the device useless to me as it was in a state waiting to join a network, so I could no interact with it at all.

Then I remembered that these devices actual support USB hardware ... like e.g. keyboards!

All it takes is USB OTG cable (or hub).

This way, you can connect the USB keyboard to the stick and still power it (the red USB cable in the picture is the keyboard).

Then, you can simply use the keyboard to connect to your WIFI, setup the stick and control it with the Fire TV app on your phone.