Как-то так:
SELECT DISTINCT `a`.`attribute_id`, `a`.`text`
FROM (
SELECT DISTINCT `p`.`id`
FROM `product` AS `p`
JOIN `product_category` AS `c` ON `c`.`product_id` = `p`.`id`
AND `c`.`category_id` = :categoryId
JOIN `product_attribute` AS `a1` ON `a1`.`product_id` = `p`.`id`
AND `a1`.`attribute_id` = :attribute1 AND `a1`.`text` = :attrValue1
JOIN `product_attribute` AS `a2` ON `a2`.`product_id` = `p`.`id`
AND `a2`.`attribute_id` = :attribute2 AND `a2`.`text` = :attrValue2
...
JOIN `product_attribute` AS `aN` ON `aN`.`product_id` = `p`.`id`
AND `aN`.`attribute_id` = :attributeN AND `aN`.`text` = :attrValueN
) AS `pr`
JOIN `product_attribute` AS `a` ON `a`.`product_id` = `p`.`id`
WHERE `a`.`attribute_id` NOT IN (:attribute1, :attribute2,... attributeN)
ORDER BY `a`.`attribute_id, `a`.`text`