Faits:
A. A.a A._ travaillait en qualité de facteur auprès de la Poste. Le 22 septembre 2006, il a été victime d'un accident de scooter qui a provoqué une fracture du tibia proximal gauche type C3 selon la classification AO et une fracture-impaction du condyle externe du fémur gauche. Le 28 septembre 2006, le docteur G._, chirurgien orthopédiste, a procédé à des réductions ouvertes et ostéosynthèses des plateaux tibiaux interne et externe ainsi qu'à une désimpaction du condyle externe du fémur gauche avec greffe osseuse (rapport du 18 octobre 2006). A._ a repris une activité au centre de tri des lettres à 25 % dès le 7 mai 2007 et à 50 % dès le 5 juin 2007. Au vu de la persistance d'une raideur articulaire au genou gauche, les docteurs G._ et S._ ont procédé, le 24 octobre 2007, à une arthrolyse arthroscopique (protocole opératoire du 24 octobre 2007). Le 25 janvier 2008, A._ a repris le travail à 25 % dans une activité de bureau effectuée à 80 % en position debout et à 20 % en position assise.
Dès le 5 mai 2008, il a travaillé à 50 % dans une activité de facteur à pied avec le moins possible de travail de bureau (position debout statique). Le 23 juillet 2008, le docteur E._, chirurgien orthopédiste et médecin d'arrondissement, a constaté une flexion/extension du genou pratiquement inchangée à la suite de l'arthrolyse arthroscopique, une démarche avec boiterie et un enraidissement important du genou gauche. Il a préconisé une activité en position alternée mais à prédominance assise avec possibilité de changer fréquemment de position, sans port de charges de plus de 5 à 10 kg et sans marche en terrain accidenté. Le docteur E._ a considéré que la capacité de travail actuelle de 50 % dans son occupation de facteur ne pouvait pas être augmentée et que, dans une activité adaptée, un horaire normal était exigible (rapport du 23 juillet 2008). En outre, le médecin d'arrondissement a fixé le taux de l'atteinte à l'intégrité à 20 % (rapport du 17 novembre 2008).
Nantie de ces avis médicaux, la Caisse Nationale suisse d'assurance en cas d'accidents (CNA) a fixé l'incapacité de gain à 29 % par comparaison des revenus et octroyé une rente du même taux. Quant à l'indemnité pour atteinte à l'intégrité, elle a repris l'évaluation du docteur E._ en la fixant à 20 % (décision du 10 mars 2009). Par décision du 13 juillet 2009, la CNA a rejeté l'opposition de l'assuré.
A.b Entretemps, A._ a déposé une demande de prestations de l'assurance-invalidité le 19 septembre 2007 auprès de l'Office AI du canton du Valais (ci-après: l'office AI) tendant à l'octroi d'une mesure d'orientation professionnelle ou de rééducation dans la même profession. A la demande de l'administration, le docteur G._, spécialiste en orthopédie et traumatologie, a attesté que l'assuré présentait une capacité de travail de 25 % maximum dans une activité de bureau en position statique et sans déplacement; ce taux était susceptible d'être augmenté à 50 % voire à 75 % dans une activité de facteur avec déplacement à pied (rapport du 4 mars 2008).
Le docteur O._, médecin au SMR, a examiné l'assuré et diagnostiqué une arthrose post-traumatique débutante ainsi qu'une ankylose post-traumatique du genou gauche (status après fracture des plateaux tibiaux interne, externe et fracture-impaction du condyle externe à gauche; ostéosynthèse, désimpaction et greffe osseuse; arthrolyse arthroscopique du genou gauche). Ce médecin a conclu à une capacité de travail nulle comme facteur mais entière dans une activité adaptée (rapport du 16 mai 2008).
Sur la base de ces éléments, l'office AI a refusé la mise en ?uvre d'une mesure de reclassement, tout en octroyant à l'assuré une demi-rente d'invalidité pour les mois de septembre à décembre 2007, puis une rente entière pour les mois de janvier à avril 2008 (décisions des 25 mars et 13 mai 2009). Ces décisions ont été confirmées par le Tribunal cantonal valaisan, Cour des assurances sociales, (jugement du 1er septembre 2009). Saisi d'un recours, le Tribunal fédéral a annulé ce jugement pour violation du droit d'être entendu (arrêt 9C_843/2009 du 30 mars 2010). La juridiction cantonale a repris la procédure et, par jugement du 21 octobre 2010, a rejeté le recours de l'assuré et confirmé les deux décisions de l'office AI. Saisi d'un nouveau recours, le Tribunal fédéral l'a rejeté (arrêt du 29 avril 2011 9C_966/2010).
B. A._ a déféré la décision sur opposition de la CNA du 13 juillet 2009 au Tribunal cantonal valaisan, Cour des assurances sociales. Conjointement à son recours, il a produit un rapport du docteur U._, spécialiste en médecine interne, du 10 juin 2009 selon lequel il présentait une boiterie relativement importante associée à l'ankylose du genou. D'après ce médecin, la position assise prolongée devenait à la longue insupportable et entraînait des lombalgies gauches d'aggravation progressive. Par ailleurs, la marche quotidienne était recommandée et indispensable pour conserver la fonction du genou, lutter contre la gonarthrose ankylosante et améliorer l'état douloureux. Une activité partagée entre le tri du courrier et sa distribution, faite à pied avec une charrette et sans port de colis, était exigible à 50 %. Pour ce médecin, la meilleure réadaptation était celle qui consistait dans l'exercice de l'activité actuelle à 50 %, laissant entendre que le patient ne pouvait pas travailler au-delà de ce taux quelle que soit l'activité exercée.
Après une interruption de la procédure, le recourant s'est prévalu d'un rapport de la doctoresse P._, spécialiste en anesthésie et en traitement de la douleur, qui l'avait examiné le 13 décembre 2010. Selon ce médecin, l'assuré présentait un état inflammatoire chronique, lequel devait être traité en priorité et ensuite les douleurs devaient être soulagées par des infiltrations (rapport du 26 mars 2011). Par la suite, la doctoresse P._ a précisé que l'activité professionnelle exercée par l'intéressé était tout à fait adaptée à son handicap; l'activité adaptée proposée par l'AI et la CNA n'était exigible qu'à 50 % (rapport du 3 juin 2011).
Après avoir pris connaissance de ces rapports, la juridiction cantonale a rejeté le recours (jugement du 14 décembre 2011).
C. A._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation. Il conclut, sous suite de frais et dépens, au renvoi de l'affaire à la juridiction cantonale ou à la CNA pour la mise en oeuvre d'une expertise pluridisciplinaire.
La CNA a conclu au rejet du recours alors que l'Office fédéral de la santé publique a renoncé à se déterminer.

Considérant en droit:
1. Le litige portant sur la question du droit du recourant à une rente d'invalidité de l'assurance-accidents, singulièrement sur le taux de celle-ci et sur le montant de l'indemnité pour atteinte à l'intégrité. Le Tribunal fédéral n'est donc pas lié par l'état de fait constaté par la juridiction inférieure (<ref-law>).
2. Conjointement à son recours, le recourant a produit trois rapports médicaux, établis par les docteurs N._ et M._, le 3 janvier 2012, par le docteur I._, le 9 janvier 2012 et par le docteur G._, le 16 janvier 2012. Il s'agit de preuves nouvelles au sens de l'<ref-law> qui ne sont pas recevables: établies postérieurement au jugement attaqué, elles ne peuvent pas résulter du jugement entrepris (ULRICH Meyer, in Basler Kommentar zum Bundesgerichtsgesetz, 2008, n° 43 ad <ref-law>).
3. 3.1 La juridiction cantonale a estimé qu'il n'y avait pas lieu de s'écarter des conclusions concordantes des rapports des docteurs O._ et E._ selon lesquelles le recourant avait une capacité de travail entière dans une activité adaptée. Celle-ci devait être principalement sédentaire (activité en position alternée mais à prédominance assise avec possibilité de changer fréquemment de position, sans port de charges supérieures à 5-10 kg et sans déplacements en terrain accidenté). Par ailleurs, les premiers juges ont retenu qu'aucun élément objectif ne permettait de dire que l'activité actuelle du recourant auprès de la poste était la seule exigible de sa part. Ils ont considéré qu'au vu des nombreux déplacements et de la station debout prolongée impliqués par l'activité de facteur, celle-ci n'était pas médicalement idéale pour la mise en valeur de la capacité résiduelle de travail de l'intéressé et risquait de péjorer davantage son état de santé.
3.2 Le recourant critique cette appréciation et considère que les rapports du docteur U._ et de la doctoresse P._ contredisent ceux des docteurs O._ et E._, lesquels n'avaient pas tenu compte des douleurs dûment attestées par les deux premiers médecins dans l'appréciation du taux d'incapacité de travail. Selon le recourant, en présence de rapports médicaux contradictoires, la juridiction cantonale avait l'obligation d'ordonner une expertise. En ne procédant pas de la sorte, elle avait violé son droit d'être entendu. Enfin, l'intéressé fait valoir que la juridiction cantonale n'a pas apprécié de façon correcte les rapports des docteurs G._, U._ et P._ et il se prévaut d'une violation du droit fédéral à cet égard.
4. Tous les médecins, qui se sont prononcés sur la capacité de travail du recourant, ont admis que celle-ci était de 50 % dans l'activité de facteur, chargé du tri et de la distribution du courrier, à l'exception des docteurs O._ et U._, qui l'ont considérée comme nulle pour cette activité.
Il reste donc à examiner la question de savoir si, comme le prétend le recourant, en exerçant son ancienne activité à 50 %, il met à profit la totalité de sa capacité résiduelle de travail. Les docteurs E._ et O._ ont admis une importante atteinte au genou gauche imposant un travail en position alternée à prédominance assise avec possibilité de changer fréquemment la position, sans port de charges de plus de 5 à 10 kg et sans déplacement en terrains accidentés (rapport docteur E._ du 23 juillet 2008). Le docteur U._ a, pour sa part, estimé la capacité de travail à 50 % dans l'activité effectivement exercée et s'est dit très surpris que le SMR X._ fasse état d'une capacité de travail de 100 % dans une activité adaptée. Il a conclu son rapport du 10 juin 2009 en précisant que "la meilleure réadaptation est celle qu'il (l'assuré) fait actuellement à 50 % avec en plus, j'espère une rente AI à 50 % entièrement justifiée".
On doit convenir que le docteur U._ n'a pas envisagé d'autres activités professionnelles avec les éventuelles incidences d'un reclassement sur la capacité résiduelle de travail. Il a uniquement indiqué qu'à son avis, aucun autre travail ne serait susceptible de diminuer l'intensité des douleurs. Une telle appréciation n'exclut pas qu'à douleurs égales, le recourant ait la possibilité d'exercer une autre activité à temps complet. La doctoresse P._ a, quant à elle, précisé que l'activité actuelle de l'assuré était adaptée à son handicap et que les activités proposées par la CNA et l'AI n'étaient exigibles qu'à 50 %. Ces appréciations ne sont toutefois pas motivées. Par ailleurs, ce médecin n'a pas exposé pour quels motifs les activités reconnues comme adaptées par les assurances, ne seraient exigibles qu'à 50 %. Enfin, dans son rapport du 6 janvier 2011, le docteur N._, spécialiste en chirurgie orthopédique à la Clinique Y._, a précisé qu'un reclassement devait être envisagé car il n'était pas possible d'attendre des traitements une amélioration importante. De cette appréciation, on doit inférer qu'un changement d'activité est envisageable et qu'il existe des occupations permettant d'éviter certains inconvénients liés à l'atteinte au genou gauche.
Au vu de tous ces éléments, il y a lieu d'admettre que les avis médicaux au dossier n'ont pas permis de mettre en doute les conclusions des docteurs O._ et E._. Il y a donc lieu de retenir, à l'instar de la juridiction cantonale, qu'il est établi au degré de la vraisemblance prépondérante, que le recourant est encore en mesure d'exercer une activité adaptée à plein temps.
Le recours doit dès lors être rejeté sur ce point.
5. 5.1 La juridiction cantonale a fixé l'indemnité pour atteinte à l'intégrité à 20 %, en se basant sur l'avis du docteur E._, qui, en application des tables d'indemnisation établies par la division médicale de la CNA, en particulier des tables 2 (atteinte à l'intégrité résultant de troubles fonctionnels des membres inférieurs) et 5 (atteinte à l'intégrité résultant d'arthroses), a inclus dans son appréciation une aggravation prévisible allant jusqu'à une arthrose moyenne.
5.2 Le recourant critique cette appréciation et affirme qu'il n'a pas été tenu compte des douleurs objectivement et médicalement constatées. En outre, il se prévaut de l'avis du docteur R._, médecin d'arrondissement, lequel fait état d'un taux supérieur à 20 %.
5.3 En l'espèce, le docteur R._, qui a examiné le recourant le 25 janvier 2011, soit postérieurement au docteur E._, a indiqué à l'assuré que l'indemnité pour atteinte à l'intégrité devait être au moins de 30 %. Sur demande de la CNA, il a confirmé cet avis par écrit le 12 avril 2011.
Cet argument, bien qu'invoqué par le recourant en procédure cantonale, n'a pas été examiné par les premiers juges. En l'absence de dossier spécifique relatif à la rechute, on ne saurait admettre, comme le demande l'intimée (cf. écriture du 14 septembre 2011), que la question de l'augmentation du taux de l'indemnité pour atteinte à l'intégrité - dans la mesure indiquée par le docteur R._ - soit examinée à un stade ultérieur. En effet, ce médecin a évoqué la rechute, annoncée par l'assuré le 30 octobre 2009, sans faire état d'une aggravation de l'atteinte. Il s'est limité à constater une absence d'amélioration à la suite de l'intervention chirurgicale à laquelle avait procédé le docteur N._, en juin 2010.
Dans ces conditions, il convient de statuer sur le taux de l'indemnité pour atteinte à l'intégrité en tenant compte de tous les éléments du dossier et non pas uniquement sous l'angle de l'<ref-law>, selon lequel une révision n'est possible qu'en cas exceptionnel, si l'aggravation est importante et n'était pas prévisible.
Le recours doit donc être admis sur ce point et l'affaire renvoyée à l'intimée pour qu'elle statue à nouveau après avoir complété l'instruction sur la question du taux de l'indemnité pour atteinte à l'intégrité.
6. Vu l'issue du litige, les frais judiciaires sont partagés deux tiers, un tiers entre A._ et la CNA (<ref-law>). Le recourant a droit à une indemnité de dépens réduite à charge de l'intimée (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis en ce sens que le jugement du 14 décembre 2011 du Tribunal cantonal valaisan, Cour des assurances sociales, et la décision sur opposition de la CNA du 13 juillet 2009 sont annulés, dans la mesure où ils fixent à 20 % le taux de l'indemnité pour atteinte à l'intégrité. Le recours est rejeté pour le surplus.
2. Le dossier est transmis à la CNA pour qu'elle complète l'instruction sur le taux de l'indemnité pour atteinte à l'intégrité et qu'elle rende une nouvelle décision.
3. Les frais judiciaires arrêtés à 750 fr. sont mis à la charge du recourant par 500 fr. et de l'intimée par 250 fr.
4. L'intimée versera au recourant la somme de 1'000 fr. à titre de dépens pour l'instance fédérale.
5. La cause est renvoyée au Tribunal cantonal pour nouvelle décision sur les dépens de l'instance cantonale.
6. 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 26 juillet 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
La Greffière: Berset