Feature Selection Algorithm for Attributes with Logical Relationships (like "AND")
Emergent pattern mining could be useful for you. In classification, emergent patterns are subsets of features which differentiate one class from the others. Look at Example 1.1 in the paper. Two feature subests, denoted $X$ and $Y$, are EPs because $X$ has large support in one class and small support in the other, and vice versa for $Y$. The nifty thing about EP mining is that it considers subsets of features instead of individual features.

Mining patterns in this way could address your problem of feature1 and feature2 having no correlation with the target class alone, but the combination feature1 AND feature2 having high correlation with the target class.

Unfortunately, I don't see any open-source software implementations on the web. However, there are a number of papers out there which implement some sort of EP mining.