Faits:
A. H.X._ et F.X._ sont propriétaires d'une ancienne ferme sise dans la commune de ... (VD). Par un "contrat d'adjudication de travaux" conclu le 28 février 2005, ils ont chargé Y._ (ci-après: l'entrepreneur) de transformer et d'agrandir le logement existant dans ce bâtiment. Le prix des travaux était alors estimé à 200'000 fr., hormis certaines prestations, tels les frais d'architecte, à rémunérer en sus. Un architecte a effectivement établi les plans nécessaires à la procédure du permis de construire. Les propriétaires ont reçu le 3 mai 2005 un devis de 257'200 fr. qu'ils ont refusé de signer. Les travaux ont néanmoins débuté et l'entrepreneur a reçu, sur le prix, deux acomptes au total de 140'000 fr. Les propriétaires ont aussi payé directement divers fournisseurs et sous-traitants.
Par lettre du 8 février 2006 émanant de leur avocat, les propriétaires, sans sommation préalable, ont signifié à l'entrepreneur qu'ils mettaient fin au contrat avec effet immédiat, "en raison notamment mais non exclusivement des innombrables défauts affectant vos prestations, et que vous n'apparaissez pas pouvoir gérer efficacement". L'entrepreneur devait établir sa facture finale et il lui était désormais interdit d'entrer dans le bâtiment.
Devant le juge de paix compétent, les propriétaires ont requis une expertise hors procès qui fut confiée à l'architecte A._. Celui-ci a rendu son rapport le 31 août 2006. Il y a énuméré de très nombreux défauts de l'ouvrage et il a aussi constaté, en stigmatisant le "dilettantisme" de l'entrepreneur, que les opérations nécessaires à la planification, à la conduite et à la surveillance d'un chantier, normalement attendues d'un entrepreneur général, n'avaient pas été accomplies.
B. Le 5 février 2008, les propriétaires ont ouvert action contre l'entrepreneur devant le Tribunal civil de l'arrondissement de La Côte. Après amplification de la demande, l'entrepreneur devait être condamné à payer 99'999 fr. à titre de dommages-intérêts. L'entrepreneur a conclu au rejet de l'action. Le Tribunal a confié une nouvelle mission d'expertise à l'architecte B._; il a en outre entendu divers témoins. Ce deuxième expert a lui aussi trouvé de nombreux et importants défauts dans l'ouvrage exécuté par l'entrepreneur.
Le Tribunal s'est prononcé le 30 novembre 2009. Il a constaté l'exécution défectueuse de l'ouvrage et jugé que les propriétaires avaient droit à des dommages-intérêts, principalement pour les frais d'élimination des défauts; accueillant l'action, il a condamné l'entrepreneur à payer aux propriétaires, créanciers solidaires, 69'098 fr. 65 avec intérêts dès le 7 mars 2008 et 30'900 fr. 35 avec intérêts dès le 20 mars 2009.
Saisie par l'entrepreneur, la Chambre des recours du Tribunal cantonal lui a donné gain de cause le 13 avril 2011. Elle a réformé le jugement en ce sens que l'action est entièrement rejetée.
Les propriétaires ont alors interjeté un recours en matière civile au Tribunal fédéral. Par arrêt du 21 décembre 2011, la cour de céans a annulé l'arrêt de la Chambre des recours et lui a renvoyé la cause pour qu'elle examine la liste des défauts et les rapports d'expertise afin de déterminer si l'entrepreneur était ou non incapable d'éliminer les défauts dans un délai convenable (arrêt 4A_518/2011, rés. in JT 2012 II 260).
Par nouvel arrêt du 5 mars 2012, la Chambre des recours a tranché dans le même sens que précédemment et derechef entièrement rejeté l'action des propriétaires. Elle a retenu que l'entrepreneur "était apte à fournir des prestations minimalistes, donc à tout le moins à la limite de l'acceptable" et que dans ces circonstances, les propriétaires auraient dû lui fixer un délai avant de se départir du contrat.
C. Les propriétaires (ci-après: les recourants) interjettent un recours en matière civile. Ils concluent principalement à la confirmation du jugement rendu le 30 novembre 2009 par le Tribunal d'arrondissement. L'entrepreneur (ci-après: l'intimé) conclut au rejet du recours.

Considérant en droit:
1. L'autorité cantonale est liée par les considérants de l'arrêt par lequel le Tribunal fédéral lui renvoie une cause. De même, s'il est ultérieurement saisi une seconde fois, le Tribunal fédéral est lié par son précédent arrêt de renvoi. Il en découle en particulier que les questions tranchées dans l'arrêt de renvoi le sont à titre définitif (<ref-ruling> consid. 2).
Dans l'arrêt de renvoi, la cour de céans a jugé que les recourants avaient résilié le contrat les liant à l'intimé, motif pour lequel ils ne pouvaient pas faire valoir des dommages-intérêts en se fondant sur l'art. 366 al. 2 CO qui suppose le maintien du contrat; cette disposition permet, lorsqu'il est "possible de prévoir avec certitude" que l'ouvrage sera exécuté de façon défectueuse, de fixer un délai à l'entrepreneur pour parer à cette éventualité avec menace de confier les travaux à un tiers. La cour de céans en a conclu que des dommages-intérêts ne pouvaient, le cas échéant, qu'être fondés sur l'art. 107 al. 2 CO. Puis elle a jugé que la question déterminante en l'espèce était celle de l'application de l'art. 108 ch. 1 CO qui dispose que la fixation d'un délai au débiteur en demeure (selon l'art. 107 al. 1 CO) n'est pas nécessaire lorsqu'il "ressort de l'attitude du débiteur que cette mesure serait sans effet"; elle a ajouté que la résiliation sans sommation était un procédé dérogatoire qui ne saurait être admis à la légère et qu'il était donc décisif de savoir si l'intimé était de façon certaine, objectivement et réellement, incapable d'éliminer les défauts de l'ouvrage dans un délai convenable.
La Chambre des recours, dans son second arrêt, a nié que l'intimé fût de façon certaine, objectivement et réellement, incapable d'éliminer les défauts de l'ouvrage dans un délai convenable; elle a retenu qu'il était capable de fournir des prestations minimalistes, à tout le moins à la limite de l'acceptable. Elle en a conclu que l'art. 108 ch. 1 CO ne s'appliquait pas et que les recourants auraient dû fixer un délai à l'intimé avant de pouvoir se départir du contrat.
2. Dans l'arrêt de renvoi, il est relevé que l'art. 108 ch. 1 CO dispensait les recourants de fixer un délai à l'intimé si ce dernier était de façon certaine, objectivement et réellement, incapable d'éliminer les défauts de l'ouvrage dans un délai convenable; il s'agit là d'une formule semblable à celle de l'art. 366 al. 2 CO, qui évoque la possibilité de "prévoir avec certitude" une exécution défectueuse. Cette dernière disposition n'implique pas une certitude absolue, qui ne se conçoit d'ailleurs guère; il est seulement exigé qu'il faille objectivement s'attendre à une exécution ou réfection défectueuse; par contre, de simples appréhensions subjectives du maître ne sont pas suffisantes (PETER GAUCH, Der Werkvertrag, 5ème éd. 2011, n° 878; FRANÇOIS CHAIX, in Commentaire romand, 2ème éd. 2012, n° 30 ad art. 366 CO; THEODOR BÜHLER, Commentaire zurichois, 3ème éd. 1998, n° 65 ad art. 366 CO). Il n'apparaît pas que la Chambre des recours ait méconnu cette notion; les recourants ne lui en font d'ailleurs pas le reproche.
3. Les recourants se plaignent uniquement d'une appréciation erronée et arbitraire des faits.
3.1 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF); en tant que cour suprême, il est instance de révision du droit et non pas juge du fait. Il peut certes rectifier ou compléter les faits s'ils ont été établis de façon manifestement inexacte, notion qui correspond à l'arbitraire, ou en violation du droit au sens de l'art. 95 LTF et ce, pour autant que la correction soit susceptible d'influer sur le sort de la cause (art. 97 al. 1 et art. 105 al. 2 LTF). Néanmoins, l'exception prévue par ces dispositions ne permet pas aux parties de rediscuter les faits de la cause comme si elles plaidaient devant un juge d'appel. Le recourant qui entend faire rectifier ou compléter l'état de fait doit expliquer de manière circonstanciée en quoi les conditions pour le faire seraient réalisées (<ref-ruling> consid. 6.2); dans la mesure où le grief a trait au caractère arbitraire de l'établissement des faits, les exigences de motivation sont celles, plus strictes, de l'art. 106 al. 2 LTF (<ref-ruling> consid. 1.4.3).
L'arbitraire ne résulte pas du seul fait qu'une solution différente de celle retenue par l'autorité cantonale pourrait entrer en considération, ou serait même préférable; le Tribunal fédéral ne s'écarte de la décision attaquée que lorsque celle-ci est manifestement insoutenable, qu'elle se trouve en contradiction claire avec la situation de fait, qu'elle viole gravement une norme ou un principe juridique indiscuté, ou encore lorsqu'elle heurte de manière choquante le sentiment de la justice et de l'équité (<ref-ruling> consid. 2.4; <ref-ruling> consid. 5.1). En matière d'appréciation des preuves et d'établissement des faits, il n'y a arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si, sur la base des éléments recueillis, il a fait des déductions insoutenables, ou encore s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée (<ref-ruling> consid. 4.1.2; <ref-ruling> consid. 2.1).
3.2 La Chambre des recours a constaté les nombreux défauts de l'ouvrage fourni par l'intimé; elle a également relevé et fait siennes les remarques critiques des experts au sujet de l'intimé, de ses qualifications et de son travail. Dans la mesure où les recourants exposent de nouveau ces éléments, ils ne présentent pas une critique de l'arrêt attaqué.
La question déterminante en l'espèce est uniquement de savoir si la Chambre des recours a versé dans l'arbitraire en considérant que ces éléments n'autorisaient pas les recourants à pronostiquer avec certitude une réfection défectueuse de l'ouvrage par l'intimé. A ce sujet, on peut certes hésiter sur les conclusions à tirer des impérities de l'intimé. Mais si l'on considère la retenue dont il faut faire preuve pour retenir une exception à l'exigence d'une sommation et si l'on tient compte du fait qu'il s'agit de poser un pronostic sur le futur qui, par la nature des choses, revêt un aspect aléatoire, on ne saurait qualifier d'insoutenable l'appréciation portée par la Chambre des recours. Les recourants ne démontrent en tout cas pas le contraire; il ne leur suffit pas d'exposer leur analyse différente de la situation pour établir l'arbitraire.
4. Les recourants ne peuvent ainsi pas se prévaloir de la dérogation de l'art. 108 ch. 1 CO qui permet exceptionnellement au créancier d'exercer sans sommation préalable les droits découlant de la demeure du débiteur; ils ne sauraient dès lors faire valoir des dommages-intérêts fondés sur l'art. 107 al. 2 CO. En outre, il a déjà été jugé que les recourants ne pouvaient pas invoquer l'art. 366 al. 2 CO pour obtenir le remboursement des coûts de réfection effectuée par des tiers. Le rejet de leur action ne viole pas le droit fédéral.
5. Les recourants succombent. Ils supportent en conséquence les frais et dépens de la présente procédure de recours (art. 66 et 68 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 5'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Les recourants sont condamnés solidairement à verser à l'intimé une indemnité de 6'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Chambre des recours du Tribunal cantonal du canton de Vaud.
Lausanne, le 10 septembre 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
La Greffière: Monti