I have slept underneath rock overhangs extensively in the SE and Appalachian foothills, solo and while leading larger groups. In fact, I have thusly practiced significantly more than using a tent in that area of the country. Many contain evidence of native American use, which is comforting as far as their longevity and safety is concerned. Some of the best sites are aided in access through the use of ropes. A few areas that can be particularly well-suited to this (although legality needs to be checked in order to preserve archaeological sites) are as follows:
Obed River Gorge, TN
Red River Gorge, KY
Big South Fork, TN
Hiawassee River Valley, TN
The biggest problems are mice, fine dusty sand that gets on everything (using ground sheets is key), and access.
Best hint: Many of the best rock-house camping places are to be found well off trail (or sometimes below).
Once I came upon two parallel ancient burial mounds inside a small, remote and well protected overhang, towards the top of a cliff band. It would have been handy to have a GPS back then, although they were not ubiquitous or even available much at that time.