Non-linear histories work just fine with git-bisect. What breaks git-bisect are histories where every commit doesn't work; for instance, if you have one commit that breaks something, and a second commit that fixes it, git-bisect won't work well.

It will work just fine, you just might have to call git bisect skip a time or two or run it more than once.

That's not "fine"; bisect takes long enough when you expect it to work consistently. And that assumes the code fails at build time, rather than mysteriously at runtime.

That also breaks the ability to do automated bisects.

I don't think it's at all unreasonable, at a minimum, to expect every individual commit to build and to pass tests.