You should have great conditions for growing many hollies, though as Todd mentioned, you might want to try other species such as Ilex cornuta which are better suited to the heat of your summers and relatively mild winters. The Blue Hollies, as a rule, aren't so well suited to the South, but the good news is that you can grow many great varieties which aren't good for us in the North, including numerous new hybrids. There is a great website from Auburn University on "Hollies for the Landscape in the Southeast" which I can recommend for you:
As for camellias and hollies, they're a great combination! They both like the same soil conditions. Gardeners up here are just beginning to discover the newer hybrid camellias, which are much more cold-hardy than the pure species. But you should be able to enjoy them all.
Thanks for the very relevant information. A lot of commercial landscapers around here (the hospital) use hollies but most residential landscapers stick to the more traditional plants. Not that holly isn't traditional, but azaleas and camellias are staples. If there are trees - they are usually dogwoods.
When I wrote this, people were still pretty skeptical about the hardy camellias.
I hope they are doing well in your area - they are such remarkable plants.