Give it another try. The current version of Nightly (v122.0a1) from the Play Store has functional sideloading for me after I unlock the "secret menu" in the settings by going to "About Nightly" and tapping the Nightly icon several times.

Before Bypass Paywalls Clean (D) existed, I was able to install Violentmonkey on Firefox for Android through the add-on collections workaround to use the Bypass Paywalls Clean userscript. You need to enable desktop mode when assembling the add-on collection (or do it from a computer) for Violentmonkey to show up as an option in the search.