Faits:
A. R._ a travaillé en qualité de peintre en bâtiment pour le compte de X._ SA. A ce titre, il était assuré contre le risque d'accident auprès de la Caisse nationale suisse d'assurance en cas d'accidents (CNA).
Le 23 novembre 2009, il s'est tordu les deux chevilles sur son lieu de travail. Consulté le même jour, le docteur B._, médecin interne au centre médical Y._, a procédé à des radiographies, lesquelles n'ont révélé aucune lésion osseuse visible. Ont été prescrits des anti-inflammatoires, des antalgiques, des anti-coagulants, des attelles Malléo sprint, des bottes de marche Vacoped ainsi qu'un arrêt de travail total d'une durée indéterminée. Une IRM pratiquée le 2 février 2010 a mis en évidence une zone de contusion au niveau interne de l'astragale sans signe de fracture, des signes en faveur d'une élongation dilacération du ligament profond collatéral interne et une interruption complète du ligament talo-fibulaire antérieur.
R._ a séjourné à la Clinique Z._ du 5 au 26 octobre 2010. Dans leur rapport du 9 décembre 2010, les docteurs F._, médecin adjoint spécialiste en médecine physique et réhabilitation, et H._, médecin-assistant, ont indiqué que le status clinique et le bilan radiologique complémentaire n'expliquaient pas l'impotence fonctionnelle. Une IRM, pratiquée le 13 octobre 2010, avait confirmé la rupture subtotale du faisceau antérieur du ligament latéral externe (le ligament talo- fibulaire antérieur) et mis en évidence un aspect épaissi et oedémacié des faisceaux profonds du ligament collatéral interne correspondant à un status post-étirement sans rupture. Il n'y avait pas d'autre lésion, oedème spongieux ou épanchement articulaire. L'assuré avait un comportement démonstratif qui s'était exacerbé à la suite de l'infiltration réalisée à la cheville gauche sur l'avis du chirurgien-orthopédiste consultant. Sur le plan psychiatrique, aucune psycho-pathologie notable n'avait été retenue et le psychiatre avait relevé de bonnes ressources chez R._, lesquelles devaient lui permettre de faire face à sa rééducation, et en cas d'échec, à une réorientation professionnelle. Les médecins ont estimé que la situation médicale était stabilisée. Ils ont proposé une reprise de l'activité professionnelle habituelle, à condition d'être chaussé correctement, dès le 27 octobre 2010.
A sa sortie, R._ s'est rendu à la permanence de l'Hôpital W._ où le médecin de garde, la doctoresse G._, a attesté une incapacité de travail de 100 % du 27 octobre au 19 novembre 2010 (en raison de la persistance des douleurs, avec charge douloureuse et déroulement impossible; rapport du 27 octobre 2010).
A l'examen du 19 novembre 2010, le docteur M._, spécialiste en médecine interne et médecine du sport à l'Hôpital W._, a confirmé, pour une durée indéterminée, l'arrêt de travail total prescrit par sa consoeur en raison d'une décompensation post-hospitalisation à la Clinique Z._ (rapport du même jour).
Par décision du 22 décembre 2010, la CNA a informé l'assuré qu'elle mettait fin au versement des indemnités journalières dès le 27 octobre 2010 et réclamait la restitution du montant de 352 fr. versé à tort. R._ s'est opposé à cette décision. Il a produit un rapport du 13 janvier 2011 du docteur M._ selon lequel une reprise professionnelle à 100 % sur un chantier n'était pas envisageable.
La CNA a transmis le dossier de l'assuré au docteur I._, spécialiste en chirurgie, médecin à son centre de compétences, lequel a indiqué qu'il était licite de conclure que l'assuré muni de chaussures montantes à son travail pouvait reprendre ses activités de peintre en bâtiment sans restriction (rapport du 7 avril 2011). Nantie de cet avis, la CNA a confirmé sa position (décision sur opposition du 19 avril 2011).
B. R._ a déféré cette décision à la Cour des assurances sociales du Tribunal cantonal valaisan. Il a versé au dossier, notamment, un rapport du 17 mai 2011 du docteur M._ ainsi qu'un rapport du 20 janvier 2011 du Service Médical Régional de l'assurance-invalidité (SMR).
Statuant par jugement du 20 février 2012, la juridiction cantonale a rejeté le recours.
C. R._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation en concluant, sous suite de frais et dépens, à l'octroi de l'indemnité journalière au-delà du 26 octobre 2010 "jusqu'à retour de sa pleine capacité de travail".
La CNA conclut au rejet du recours tandis que l'Office fédéral de la santé publique a renoncé à se déterminer.

Considérant en droit:
1. Le litige porte sur le point de savoir si l'intimée était fondée à supprimer avec effet au 27 octobre 2010 l'indemnité journalière versée au recourant.
2. Selon l'<ref-law>, l'assuré totalement ou partiellement incapable de travailler (<ref-law>) à la suite d'un accident a droit à une indemnité journalière. Le degré de l'incapacité de travail doit être fixé sur la base de la profession exercée jusqu'alors, aussi longtemps qu'on ne peut raisonnablement exiger de l'assuré qu'il mette à profit sa capacité de travail résiduelle dans une autre branche professionnelle (obligation de diminuer le dommage; cf. <ref-ruling> consid. 4.2 p. 463; <ref-ruling> consid. 1d p. 283; voir également l'art. 6, deuxième phrase, LPGA). Si une activité de substitution est exigible, un laps de temps suffisant compris entre trois et cinq mois doit alors être imparti à l'assuré pour lui permettre de retrouver un emploi adapté à son état de santé (SJ 2000 II consid. 2b p. 440). A l'issue de ce délai, le droit à l'indemnité journalière dépend de l'existence d'une perte de gain éventuelle imputable au risque assuré. Celle-ci se détermine par la différence entre le revenu qui pourrait être obtenu sans la survenance de l'éventualité assurée dans la profession exercée jusqu'ici et le revenu qui est obtenu ou pourrait raisonnablement être réalisé dans la nouvelle profession (ATF <ref-ruling> consid. 3c in fine p. 286; UELI KIESER, ATSG-Kommentar, 2ème éd., 2009, n° 26 ad art. 6). La perte de gain chiffrée en pour cent donne ainsi le taux de l'incapacité de travail résiduelle.
3. 3.1 Les premiers juges ont fait leurs les appréciations du docteur I._ et des médecins de la Clinique Z._; ils ont ainsi retenu que l'état de santé de l'assuré était stabilisé et que l'intéressé était à même de faire valoir une pleine capacité de travail dans son activité de peintre en bâtiment (moyennant le port de chaussures adéquates) ou du moins dans une activité adaptée (évitant la marche en terrain irrégulier). Ils ont considéré qu'au regard du large éventail d'activités simples et répétitives que recouvrent les secteurs de la production et des services, un certain nombre d'entre elles étaient légères et adaptées aux limitations de l'assuré.
3.2 Le recourant fait grief à la juridiction cantonale d'avoir écarté, en particulier, les conclusions des docteurs M._, G._ ainsi que celles du SMR, au profit des avis des médecins de la CNA.
3.3 En l'espèce, ces médecins s'opposent sur différents points. Pour le docteur I._ - lequel confirme le rapport des médecins de la Clinique Z._ - l'examen clinique montre qu'au plan fonctionnel, la cheville avait non seulement récupéré sa stabilité, mais également en grande partie sa mobilité; l'intéressé pouvait reprendre ses activités de peintre en bâtiment sans restriction, sauf à porter des chaussures montantes à son travail. Pour les médecins de l'Hôpital W._ et, notamment, pour le docteur M._, on trouve chez R._ "un nombre de signes objectifs montrant des lésions tissulaires subies lors de son accident" et l'assuré "présente du point de vue subjectif une gêne importante rendant une reprise professionnelle à 100 % sur un chantier inenvisageable actuellement" (rapport du 13 janvier 2011). Le docteur M._ a précisé par la suite que si l'évolution radiologique était plutôt bonne, l'évolution du patient dans son ensemble était peu favorable et ne laissait pas présager une reprise du travail à temps complet du jour au lendemain (rapport du 17 mai 2011).
Pour sa part, la doctoresse U._ du SMR considère que l'assuré doit éviter la marche en terrain irrégulier (instable, accidenté, escaliers, échafaudages). Elle estime que la fragilité des deux chevilles entraîne un risque d'invalidité à moyen terme, raison pour laquelle elle retient une incapacité de travail de 20 % dans l'activité habituelle de peintre en bâtiment et préconise des mesures professionnelles.
3.4 En matière d'appréciation des preuves, le juge doit examiner objectivement tous les documents à disposition, quelle que soit leur provenance, puis décider s'ils permettent de porter un jugement valable sur le droit litigieux. Il ne peut écarter un rapport médical au seul motif qu'il est établi par le médecin interne d'un assureur social, respectivement par le médecin traitant (ou l'expert privé) de la personne assurée, sans examiner autrement sa valeur probante. Dans une procédure portant sur l'octroi ou le refus de prestations d'assurances sociales, le Tribunal fédéral a récemment précisé que lorsqu'une décision administrative s'appuie exclusivement sur l'appréciation d'un médecin interne à l'assureur social et que l'avis d'un médecin traitant ou d'un expert privé auquel on peut également attribuer un caractère probant laisse subsister des doutes suffisants quant à la fiabilité et la pertinence de cette appréciation, la cause ne saurait être tranchée en se fondant sur l'un ou sur l'autre de ces avis et il y a lieu de mettre en oeuvre une expertise par un médecin indépendant selon la procédure de l'<ref-law> ou une expertise judiciaire (<ref-ruling>).
3.5 Sur le vu des opinions divergentes des médecins en ce qui concerne plus spécialement l'étendue de l'incapacité de travail du recourant dans sa profession, on ne saurait sans plus retenir que celui-ci a une pleine capacité de travail dans sa profession de peintre en bâtiment. Par ailleurs, même si l'on admet que le recourant pourrait exercer en plein une autre activité adaptée - encore qu'il n'apparaît pas que la CNA lui ait imparti un délai approprié pour trouver une telle activité - on ignore s'il subirait ou non une perte de gain (cf. supra consid. 2). Les premiers juges, en effet, n'ont procédé à aucune comparaison des revenus.
3.6 La cause sera par conséquent renvoyée à la CNA afin qu'elle mette en oeuvre une expertise au sens de l'<ref-law> et qu'elle rende nouvelle décision sur le droit aux prestations de l'assuré. Dans cette mesure le recours est bien fondé.
4. L'intimée qui succombe supportera les frais judiciaires (<ref-law>). Le recourant, qui est représenté par les Syndicats chrétiens interprofessionnels du Valais, peut prétendre une indemnité de dépens à la charge de l'intimée (<ref-law> et art. 9 du règlement sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral, du 31 mars 2006 [RS 173.110.210.3]; cf. arrêt 8C_589/2009 du 28 juin 2010 consid. 5.2 et les arrêts cités).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis en ce sens que le jugement du 20 février 2012 de la Cour des assurances sociales du Tribunal cantonal valaisan de même que la décision sur opposition du 19 avril 2011 sont annulés, la cause étant renvoyée à la CNA pour instruction complémentaire au sens des motifs et nouvelle décision.
2. Les frais judiciaires, arrêtés à 750 fr., sont mis à la charge de l'intimée.
3. L'intimée versera au recourant la somme de 1'500 fr. à titre de dépens pour la dernière instance.
4. La cause est renvoyée au Tribunal cantonal valaisan, Cour des assurances sociales, pour nouvelle décision sur les dépens de la procédure cantonale.
5. Le présent arrêt est communiqué aux parties, au Tribunal cantonal valaisan, Cour des assurances sociales, et à l'Office fédéral de la santé publique.
Lucerne, le 27 août 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
La Greffière: Berset