En fait la justification pour utiliser un setter, ce serait que la dépendance injectée soit facultative (au sens où la classe est 100% fonctionnel sans, sans exception ou effet de bord), cela dit c'est loin d'être souvent le cas.
Cependant, l'injection par setter s'est démocratisée avec les conteneurs IOC, c'est à dire des outils comme Spring ou Guice qui peuvent construire des objets et injecter leurs attributs selon une configuration pré-établie. Le développeur peut affirmer avec plus ou moins d'assurance que les classes ne seraient jamais instanciées à l'aide d'un new, elles peuvent même avoir un constructeur par défaut non public pour s'en assurer.
Mais en général, il y a peu de justifications de nos jours de ne pas laisser les dépendances dans le constructeur, et évt de les déclarer private final.
Comme tu l'expliques très bien, c'est rarement une bonne idée de risquer de laisser des objets dans un état de merde après la construction. Quant au builder... ça t'amène pas forcément grand chose par rapport à une factory car tu as rarement besoin de construire tes classes entièrement à la carte. Tu auras peut être une configuration de Test avec des mocks, et une configuration de Prod avec des services réels, rarement une infinité de mix possibles qui te demandent la flexibilité d'un builder en pratique.