All of this can only work with a clean git history containing only working commits.
This isn't really true.
You can use git bisect skip to skip commits that can't be evaluated. So if you are tracking down the failure of test foo and this commit fails to build, you can skip it.
If all merged commits are green then you can use --first-parent to avoid testing inside a development branch. This way you can identify which merge caused the issue, even if other merges had broken commits.
So it is easier in general if you have all working commits, but it isn't necessary. Really as long as you have green history on your main branch you will be able to get good results without much effort. I would highly suggest using some sort of merge-queue based workflow to ensure that the master branch is always green.
I would generally prefer using --first-parent rather than forcing squashing. As smaller commits can be much easier to understand and the fact that commit IDs don't change when being merged can make it much easier to manage stacked PRs and hotfix backporting.