Since the human visual system is so highly sensitive to faces I think the best approach here would be to apply a facial detection algorithm, then boost the energy for the regions where faces are detected.

Basically you'd apply a heuristic that because faces are so special to the human visual system, the perceived energy of a face is higher than the pixels would otherwise indicate.

This would make seams avoid altering any faces in the scene.