actually, you do not lose any rights when you have a verbal agreement rather than a written agreement. It is harder to prove any claim made but your rights are equivalent.

It would appear you have a month to month tenancy. As such, the LL can change the rules with proper notice, which would simply be notice prior to the month the new rules would be applicable.

Assuming we can find a place and can move, what's the best legal way we can move out and not screw ourselves over payment-wise and lawsuit-wise?
simply provide proper notice prior to moving (I would have to check for actual requirements but quite likely it would be either 30 days or one rental period).

then, be sure there are no damages you caused the LL has to deal with.

Then leave no later than the last day of the period of notification and you should be presented with no problems.