Есть 2 варианта.
1. Банальный "в лоб" - получить все категории, циклом по ним пройтись и в каждом итерации запрашивать посты из этой категории. Все стандартными средствами. Не супер-быстро, но будет работать. Если воспользоваться кешированием результатов в transients, то будет съедобно.
Смотрите код тут.
2. Выполнить кастомный запрос в БД через $wpdb и дальше разобрать результаты обычным foreach. Запрос получится примерно с 4мя JOIN, но вернет все что надо в сгруппированном виде.
Пример смотрите тут.