Yes, play the multiballs. Mayhem and Carnage (either stacked or separate) should easily reach level 10 to start fighting the bosses.
Yes, beating a boss via Mayhem doesn’t count as a boss fight for purposes of enabling a host change.
You do get stuck in jail if you somehow finish two hosts on one ball without reaching level 10. But you should have played the multiballs by then. Completing 6 mini-modes for that is always enough to qualify 3 Mayhem locks. If you declined Mayhem and now need to shoot more mini-modes just for the locks, that was your own doing.
The worse jail is when you did beat the first-tier boss (either normally or in Mayhem) but are now stuck between level 10 and 20 so can’t do Grendel yet. It’s not a bug, it’s the design working as intended, but the design is very frustrating. The best way is to avoid the problem in the first place by getting to 20, during a stacked Mayhem-Carnage MB with both 2x exp multipliers (grid box and 3 left-side locks.) If you do end up in this situation stuck short of level 20, generally the one thing you can do is more Carnage modes; Blood Lust is worth good XP, and it’s not that hard to turn it all the way over to a second instance of Carnage MB.