I finally got the answer but thanks a lot to @Priyesh comment and this link: "Not in" constraint using JPA criteria
After edit I realized that it the goal is little different (see the edited post).
So Subquery had to be used, see: JPQL, How to NOT select something
Just for anybody, here is the Criteria API Query that worked for me, but it's basically just rewritten JPQL query above.
Predicate wantedToBePresentTags = cb.lower(rTag.<String>get("name")).in(cb.parameter(List.class, "tagList"));
Subquery sq = criteriaQuery.subquery(TestExecution.class);
Root sqRoot = sq.from(TestExecution.class);
Join<TestExecution, Tag> sqTag = sqRoot.joinCollection("testExecutionTags").join("tag");
sq.select(sqRoot.get("id"));
sq.where(cb.lower(sqTag.<String>get("name")).in(cb.parameter(List.class, "excludedTagList")));
Predicate excludedTags = cb.not(rExec.get("id").in(sq));
...
criteriaQuery.where(cb.and(wantedToBePresentTags, excludedTags));
Hope that this helps somebody! :-)