I've seen some apps are using alternating rows background in their predicate editors, but I can't figure out how they do it.
Most of them pre-date NSPredicateEditor, and some (such as the one in iTunes) aren't even Cocoa. Some may be NSTableViews or NSOutlineViews with very complicated custom cells; others may be fully custom, descending directly from NSView.
Without being able to tell NSPredicateEditor to do it or reliably subclass NSPredicateEditor to do it (even if it has private methods you can override to customize its drawing, you can't rely on those existing), those are the only ways.
I don't think it's worth it. NSPredicateEditor and NSRuleEditor give you a lot of functionality for free or nearly so, and their default appearance is probably how Apple wants those views to look in all apps in the future. In this case, I say it's best to go with the flow.