Você pode usar agregação aqui:
SELECT job_id
FROM skill_usage
WHERE skill_id IN (3, 4)
GROUP BY job_id
HAVING MIN(skill_id) <> MAX(skill_id);
Essa consulta deve se beneficiar do seguinte índice:
CREATE INDEX idx ON skill_usage (skill_id, job_id);
Tanto o
WHERE e HAVING cláusulas, conforme escritas, são sargable , e deve ser capaz de tirar proveito desse índice. 
