Для "сложных конструкций" без парсинга HTML - никак. Самый простой путь - preg_replace_callback на все CSS селекторы (включая .div .child, .div > .child, .div.child и тд), в колбеке - проходимся по HTML так, как это бы сделал css engine, меняем все что нужно и возвращаем такую же измененную строку.
В любом случае это извращение, имхо) Либо вариант проще - менять лишь названия без парсинга, при этом учитывая, что в .div .child, .div > child, .div.child будут заменены лишь названия, и для каждого типа div всегда будет равен одному хэшу.