Rotated object detection by Viola jones Algorithm
You are correct, Haar features, as well as LBP and HOG are not rotation invariant. I have experimented with vision.CascadeObjectDetector in MATLAB's Computer Vision System Toolbox, and found that the face detector model it comes with can tolerate about 15 degrees of in-plane rotation.

So if you want to handle in-plane rotation, the easiest thing is to rotate the image by 15 degree increments and run the detector each time.  If you are talking about out-of-plane rotation, then you would need multiple detectors, such as the frontal and profile detectors that come with MATLAB.

There is another possibility. If you need to detect the faces in video, then you can handle rotations and even partial occlusions by tracking them using KLT.  See this example.