perhaps you could preprocess the shape using the Binary Space Partitioning (BSP) algorithm. there’s a step in the algorithm that finds polygons that would cause z-sorting conflict and splits them along the exact line you need to resolve the conflict. you end up with a data structure that gives you the z sorting order for any camera angle.
Handling intersecting polygons, as you said, is a bit more complex, but for overlapping polygons it's possible to find the Z-order robustly by computing the intersections with the line of sight.