Faits:
A. K._, né en 1965, a travaillé en qualité de manoeuvre au service de l'entreprise X._ et était, à ce titre, assuré contre le risque d'accidents professionnels et non professionnels auprès de la Caisse nationale suisse d'assurance en cas d'accidents (ci-après: CNA). Le 10 janvier 2005, il a consulté la doctoresse D._ au Centre médical Y._, laquelle a attesté une incapacité de travail de 100% pour la période du 10 au 16 janvier 2005 (attestation du 10 janvier 2005). Le 11 février 2005, la doctoresse R._, médecin de famille au Centre médical Y._, a fait état d'une incapacité de travail pour cause de maladie de 100% pour la période du 14 au 28 février 2005. Elle n'a pas décrit le trouble dont souffrait son patient.
Le 16 février 2005, l'entreprise X._ a rempli une déclaration d'accidents LAA. Il en ressort que, le 13 juillet 2004, alors que l'employé tapait avec une masse sur un mur: « Il a reçu un bloc de béton sur le coude (a continué à travailler jusqu'à ce jour sans rien dire, mais la douleur devenue trop vive, a consulté un médecin )». Sous la rubrique « type de lésion », l'employeur a simplement signalé qu'une opération était prévue. Le 1er mars 2005, K._ a été opéré d'une épicondylite du membre supérieur gauche par le docteur H._, spécialiste en chirurgie de la main. Invité le 2 mars 2005 par la CNA à lui fournir des informations sur les circonstances de l'accident, K._ a répondu par lettre du 9 février 2005 (recte: 9 mars 2005) qu'un bloc de béton avait chuté sur le coude droit.
Dans un rapport médical LAA du 22 mars 2005, la doctoresse R._ a diagnostiqué une épicondylite post-traumatique; elle a précisé que le patient avait chuté et s'était réceptionné sur le coude gauche. L'incapacité de travail était totale depuis le 10 janvier 2005.
Le 29 mars 2005, le docteur H._ a posé le diagnostic de status après cure chirurgicale pour « épicondalgie » du membre supérieur gauche. Interrogé par la CNA sur l'évolution du cas, le docteur H._ a répondu que l'assuré ressentait toujours des douleurs dans le coude et que l'extension était encore incomplète; son état n'était pas stabilisé, mais un changement de profession ne s'avérait pas nécessaire. Dans un rapport du 27 avril 2005, la doctoresse R._ a déclaré que K._ souffrait de douleurs à la palpation de l'épicondyle gauche avec diminution de la motricité. Elle a expliqué qu'elle avait d'abord attribué les plaintes de son patient à la maladie, car celui-ci avait omis de lui indiquer l'origine traumatique, laquelle remontait au mois de juillet 2004.
Après avoir pris connaissance du dossier, le docteur G._, médecin d'arrondissement de la CNA, a indiqué que la relation de causalité entre les troubles décrits par les docteurs R._ et H._ et l'accident était exclue: une contusion au coude droit ne pouvait causer d'épicondyle à gauche (note du 29 avril/3mai 2005).
Par décision du 11 mai 2005, la CNA a refusé d'allouer des prestations à l'assuré, au motif qu'il n'y avait pas de lien de causalité pour le moins probable entre les troubles à l'origine de l'arrêt de travail à partir du 10 janvier 2005 et l'accident du 13 juillet 2004. Il n'y avait ni suite d'un accident couvert, ni lésion corporelle assimilée à un accident. Par lettre du 19 mai 2005 (non signée), le docteur H._ a demandé à la CNA de reconsidérer le refus de prise en charge du cas, au motif que l'assuré était « en pleine réévaluation ».
A l'appui d'une électroneuromyographie, le docteur O._, spécialiste en neurologie, a conclu à l'absence de signe lésionnel du nerf radial gauche (tant moteur que sensitif) et à une atteinte connue du nerf médian gauche aux carpes. Il a indiqué que l'évolution post-opératoire n'était pas favorable, avec persistance de douleurs au coude qui était modérément tuméfié. L'assuré condamnait son bras gauche, portait une attelle au poignet et ne faisait pratiquement plus rien avec ce bras. Il éprouvait de la difficulté à l'extension du poignet et des doigts, provoquant une douleur à la fois au poignet et dans la région de l'épicondyle. La palpation de ce dernier était sensible, de même que celle du poignet. La sensibilité distale de la main était perturbée de manière non spécifique. La réponse idio-musculaire des extenseurs radiaux était normale et symétrique. Le docteur O._ a conclu son analyse par ces termes: «Nous restons dans cette situation douloureuse et non résolue de son bras gauche, sans atteinte neurogène à même de l'expliquer » (rapport du 30 mai 2005).
Le 9 juin 2005, l'assuré a formé opposition auprès de la CNA. A cette occasion, il a déclaré ce qui suit: « Je me trouvais au travail. Je voulais faire tomber un mur. Le mur est tombé sur moi et je me suis protégé avec le coude gauche pour ne pas le recevoir et c'est alors que j'ai reçu un grand bloc de béton sur le coude gauche et que je suis tombé en arrière. Je saignais au coude, alors je me suis bandé avec un t-shirt. J'ai continué à travailler mais pas avec la même force jusqu'au 10 janvier 2005. Le 10 janvier 2005, je me suis rendu (à la base pour une grippe) au Centre médical Y._. Etant donné que j'avais encore mal à mon coude gauche, on m'a fait des piqûres. Par la suite, j'ai vu le docteur H._ qui m'a proposé une intervention. J'ai été en arrêt de travail pour l'accident dès le 17 janvier 2005. Je demande à la CNA de reconsidérer mon cas, car il s'agit d'un accident et de prendre en charge cette affaire ainsi que l'intervention du 1er mars 2005. »
Interrogé à nouveau sur le cas par la CNA, le docteur G._ a confirmé sa position le 13/16 juin 2005.
Le 21 juin 2005, le docteur B._, spécialiste en rhumatologie, a rendu un rapport d'expertise médicale à la demande de l'assurance-maladie. Selon ce médecin, l'assuré se plaignait de douleurs permanentes au coude gauche et signalait des troubles neurologiques sous forme de diminution de la sensibilité. Le tableau clinique aurait éventuellement pu correspondre d'un point de vue neurologique à une lésion du nerf radial, mais celle-ci a été exclue par le docteur O._. Les trois électroneuromyographies (des 6 avril, 30 mai et 8 juin 2005) permettaient d'écarter une atteinte neurogène responsable de ces troubles. En ce qui concerne le flexum, il était difficile à expliquer: les radiographies du coude ne montraient pas de lésion significative. Avant d'exclure totalement l'implication des lésions locales dans les troubles du patient, le docteur B._ a proposé une IRM du coude, afin d'écarter définitivement un processus de type algodystrophie, voire une capsulite rétractile, qui semblait cependant extrêmement peu probable (et plus rare que pour l'épaule). Si l'IRM devait exclure ces deux hypothèses, il faudrait alors envisager deux possibilités: une pathologie psychiatrique (telle qu'un trouble somatoforme douloureux) ou alors une simulation.
Le 26 septembre 2005, l'assuré a été examiné par le docteur G._. Il ressort des conclusions de ce médecin que les contradictions entre la déclaration d'accident mentionnant le coude gauche et la lettre du 9 mars 2005 évoquant le coude droit étaient le fruit d'une simple erreur de l'assuré. Le médecin a souligné qu'après l'événement, l'assuré avait continué à travailler sans gros problème apparent pendant six mois, dans une activité lourde. Il a qualifié le résultat de catastrophique et nié que la situation clinique décrite à partir de janvier 2005 ait été une conséquence certaine ou vraisemblable de l'accident survenu le 13 juillet 2004. Il a fait remarquer que le traumatisme décrit par l'assuré a provoqué une contusion sur la face postérieure du coude. Or une telle contusion ne pouvait être à l'origine d'une symptomatologie située au niveau de l'épicondyle, celui-ci étant placé en position latérale. Si une lésion significative était tout de même survenue au niveau de la musculature d'extension du poignet, au coude, il était peu vraisemblable qu'une telle lésion ait été compatible avec la poursuite du travail de manoeuvre pendant six mois (rapport du 4 octobre 2005).
Par décision du 24 octobre 2005, la CNA a rejeté l'opposition de l'assuré à sa décision du 11 mai précédent, en retenant que les troubles étaient sans lien de causalité avec l'accident.
B. Par acte du 9 février 2006, K._ a déféré cette décision au Tribunal cantonal des assurances sociales de la République et canton de Genève. Il concluait à ce que son cas soit pris en charge par l'assurance-accidents dès le 17 février 2005 (à titre principal: sans limitation de date) et, à titre subsidiaire, « jusqu'à la fin de la durée moyenne de remise en état ». Quand bien même la situation clinique postopératoire n'aurait plus de lien direct avec l'accident, il incombait selon lui à la CNA de répondre des troubles typiques et habituels qu'il avait subis avant et après l'intervention chirurgicale pendant la durée moyenne de remise en état, en application des tabelles prévues à cet effet pour les différentes pathologies. A l'appui de ses allégations, il a produit une lettre du 8 février 2006 adressée par le docteur H._ à son mandataire. Selon ce médecin « il me semble que l'événement du 13 juillet 2004 n'est pas contesté en tant qu'accident, car il satisfait aux quatre critères légaux. Dès la première consultation, il a été posé le diagnostic d'épicondalgie, vraisemblablement post-traumatique ».
En cours de procédure, l'éventualité de l'examen complémentaire préconisé par le docteur B._ dans son rapport du 21 juin 2005 a été soumis à la division médicale de la CNA. Dans une appréciation du 5 avril 2006, le docteur I._, spécialiste en chirurgie orthopédique, a estimé, notamment, que ni le diagnostic d'algodystrophie du coude ni celui de raideur (capsulite rétractile) post-traumatique n'étaient vraisemblables, si bien qu'il était inutile de pratiquer d'autres examens sous forme d'IRM ou de scintigraphie osseuse. Le docteur I._ a également exposé les raisons qui ne permettaient pas de retenir le caractère traumatique de l'épicondylite, seul trouble organique diagnostiqué et traité depuis lors.
Invitée à se prononcer, la CNA a conclu au rejet du recours. Elle a fait en particulier remarquer qu'elle avait renoncé à instruire la problématique psychique, faute d'un lien de causalité adéquate avec l'accident qu'elle qualifiait de peu de gravité.
Après avoir recueilli la réplique de l'assuré et la duplique de la CNA, la juridiction cantonale a rejeté le recours par jugement du 7 décembre 2006.
C. K._ a interjeté un recours de droit administratif contre ce jugement, dont il a demandé l'annulation en reprenant les conclusions formées devant la juridiction cantonale, sous suite de frais et dépens. Par ailleurs, il a sollicité le bénéfice de l'assistance judiciaire gratuite. Le 8 février 2007, A._, assistante sociale au Département de psychiatrie de l'Hôpital Z._ a adressé au Tribunal fédéral une lettre co-signée par K._ contenant des précisions sur la situation financière de l'assuré.
La CNA a conclu 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. La loi fédérale sur le Tribunal fédéral du 17 juin 2005 (LTF; RS 173.110) est entrée en vigueur le 1er janvier 2007 (RO 2006 1205, 1242). L' acte attaqué ayant été rendu avant cette date, la procédure reste régie par l'OJ (<ref-law>; <ref-ruling> consid. 1.2 p. 395).
2. Dans la procédure de recours concernant l'octroi ou le refus de prestations d'assurance, le pouvoir d'examen du Tribunal fédéral en matière d'assurance-accidents n'est pas limité à la violation du droit fédéral - y compris l'excès et l'abus du pouvoir d'appréciation - mais s'étend également à l'opportunité de la décision attaquée. Le tribunal n'est alors pas lié par l'état de fait constaté par la juridiction inférieure, et il peut s'écarter des conclusions des parties à l'avantage ou au détriment de celles-ci (art. 132 OJ dans sa teneur en vigueur jusqu'au 30 juin 2006).
3. Le litige porte sur le droit du recourant à des prestations de l'assurance-accidents, singulièrement sur la question de savoir s'il existe un lien de causalité entre les troubles de santé au coude, ainsi que l'incapacité de travail que l'assuré a présentée et l'accident du 13 juillet 2004.
4. Le jugement entrepris expose correctement les règles légales à la solution du litige (<ref-law>) ainsi que les principes jurisprudentiels (relatifs notamment à la causalité naturelle) applicables au cas. On peut dès lors y renvoyer.
Par ailleurs, on rappellera que d'après la jurisprudence, le juge peut accorder valeur probante aux rapports établis par les médecins de la CNA aussi longtemps que ceux-ci aboutissent à des résultats convaincants, que leurs conclusions sont sérieusement motivées, que ces avis ne contiennent pas de contradictions et qu'aucun indice concret ne permet de mettre en cause leur bien-fondé (cf. <ref-ruling> consid. 3b/ee p. 353 sv.).
5. 5.1 La juridiction cantonale a nié l'existence d'un lien de causalité naturelle entre les troubles au coude gauche dont souffre le recourant et l'accident du 13 juillet 2004. Elle s'est fondée pour cela sur les rapports des docteurs O._, B._, G._ et I._.
5.2 A l'instar de la juridiction cantonale, le Tribunal fédéral n'a aucune raison de s'écarter des conclusions des médecins précités. Les lésions post-traumatiques au coude gauche ont été évoquées pour la première fois le 22 mars 2005 par la doctoresse R._, soit plus de huit mois après l'accident. Après l'événement du 13 juillet 2004, le recourant a continué à travailler six mois, sans gros problème apparent, dans une activité lourde. Avant qu'il n'ait pu être examiné par les médecins de la CNA, l'assuré a été opéré de son épicondylite (le 1er mars 2005). Les suites de cette intervention chirurgicale ont été qualifiées de catastrophiques par le docteur G._, avec une exclusion fonctionnelle du membre supérieur qui ne s'expliquait pas par les éléments objectifs du status (rapport du 4 octobre 2005, p. 4).
Le 30 mai 2005, le docteur O._ a exclu la présence d'une atteinte lésionnelle du nerf radial gauche sur la base d'une électroneuromyographie. Pour sa part, le docteur B._ a écarté la présence d'une atteinte neurogène responsable des troubles de l'assuré. Au terme d'une analyse fouillée, ce médecin a émis l'hypothèse qu'il pouvait s'agir d'une atteinte somatique (très peu probable, sous forme d'algodystrophie ou de capsulite rétractile) et proposé une IRM du coude pour éliminer définitivement ces cas de figure ou d'une atteinte psychique (trouble somatoforme douloureux) ou encore de simulation.
Les deux diagnostics d'atteinte somatique ont été écartés de manière convaincante par le docteur I._ dans son rapport du 5 avril 2006. Après avoir rappelé que l'algodystrophie isolée du coude est rare (tout comme l'épicondylite post-traumatique), le médecin de la CNA a constaté que l'on n'observe pas chez l'assuré d'amyotrophie significative au niveau du bras. L'oléocrane, l'épicondyle et toute la musculature épicondylienne sont douloureux à la palpitation, mais pas le reste du coude. Ce n'est pas tant la mobilisation du coude, mais bien la tentative d'en préciser l'éventuelle limite en extension qui déclenche apparemment des douleurs chez l'assuré. En outre, si l'on se fonde sur la notion que le flexum est de manifestation chronique, il devrait nécessairement se traduire par une amyotrophie bien plus marquée au niveau du bras que de l'avant-bras. En effet, une amyotrophie du triceps devrait être présente: elle n'a été observée ni par le docteur B._, ni plus tard par le docteur G._. D'autre part, celui-ci a noté lors de la mesure des périmètres qu'il y avait une différence au détriment du côté gauche d'un centimètre au niveau du bras et de l'avant-bras, ce qui est une observation normale chez un droitier, alors que la flexion-extension s'était péjorée dans l'intervalle pour n'atteindre plus que 110-60-0° et ce toujours en l'absence d'une amyotrophie significative du bras, malgré les trois mois écoulés depuis l'examen pratiqué par le docteur B._. En outre, les photographies prises par le docteur G._ montrent que le trouble fonctionnel n'intéresse pas le coude isolément, mais également la main, qui est maintenue en hyperflexion à près de 90°. Ni dans l'algodystrophie du coude, ni dans le syndrome épaule-main un trouble fonctionnel de ce type n'est observé. Il faut dès lors conclure à une très probable origine fonctionnelle, donc non organique, du tableau clinique. Par ailleurs, la capsulite rétractile (ou raideur du coude) pouvait être écartée sans autre, dès lors que l'assuré n'avait subi ni fracture intra-articulaire, ni luxation du coude. En d'autres termes, l'hypothèse d'une rétraction capsulaire post-traumatique ou d'une atteinte du muscle brachial suite à une luxation du coude était exclue. Au vu de ces éléments, ni l'un ni l'autre des diagnostics (différentiels) possibles évoqués par le spécialiste en rhumatologie n'étaient vraisemblables, de sorte que des investigations complémentaires étaient inutiles. En définitive, l'origine du trouble fonctionnel décrit par le docteur B._ et illustré par le docteur G._ ne se rattachait pas à une pathologie post-traumatique connue de l'appareil locomoteur.
5.3 Le recourant fait grief à la juridiction cantonale de ne pas avoir pris en considération les appréciations des médecins qui l'avaient examiné avant l'opération du 1er mars 2005, soit les avis de la doctoresse R._ (attestation du 11 février 2005 précisée par le rapport médical LAA du 22 mars 2005) ainsi que ceux du docteur H._ du 29 mars 2005 et du 8 février 2006. Or, en comparaison avec les appréciations des autres médecins (cf. consid. 5.1), les avis des deux médecins traitants ne sont pratiquement pas motivés quant à l'origine traumatique de l'atteinte subie par l'assuré. Dans son attestation du 11 février 2005, la doctoresse R._ a simplement attesté une incapacité de travail et dans le rapport médical LAA, elle a posé un diagnostic. Il en va de même des avis du docteur H._. Quoi qu'il en soit, le point de vue du docteur H._ n'est pas aussi catégorique que l'affirme le recourant. Ainsi, il ressort de l'expertise du docteur B._ que le docteur H._ s'était montré perplexe face au tableau clinique développé par le patient et qu'il ne parvenait pas à faire le lien entre les plaintes et une lésion anatomique. Le docteur B._ a également indiqué qu'il avait exposé ses conclusions au docteur H._ sans que celui-ci n'émette d'objections ou lui fasse part de son désaccord. Dans ces conditions, les avis des médecins traitants ne sauraient emporter la conviction. De toute manière, le juge statue en matière de fait au degré de la vraisemblance prépondérante. Or, ainsi que les premiers juges l'ont exposé, si l'existence d'un rapport de cause à effet entre l'accident paraît possible, elle ne peut pas être qualifiée de probable dans le cas particulier si bien que le droit à des prestations fondées sur l'accident doit être nié.
5.4 On ajoutera que la responsabilité de la CNA ne serait pas engagée, à supposer que l'assuré présente également une affection psychique, sous la forme d'un trouble somatoforme douloureux, évoquée par le docteur B._. Même si l'on devait retenir, comme le soutient le recourant, l'existence d'un rapport de causalité naturelle entre ces troubles et l'accident, le lien de causalité adéquate ferait de toute manière défaut. En effet, le droit a des prestations découlant d'un accident assuré suppose également entre l'événement dommageable de caractère accidentel et l'atteinte à la santé, un lien de causalité adéquate. Il faut que, d'après le cours ordinaire des choses et l'expérience de la vie, l'accident soit propre à entraîner un effet du genre de celui qui s'est produit, la survenance de ce résultat paraissant de façon générale favorisée par une telle circonstance (<ref-ruling> consid. 3.2 p. 181 et la référence), au point que le dommage puisse encore équitablement être mis à la charge de l'assurance-accidents eu égard aux objectifs poursuivis par la LAA (cf. <ref-ruling> consid. 3 p. 100 ss et les références). Selon la jurisprudence, l'existence d'un lien de causalité adéquate entre un accident insignifiant ou de peu de gravité et des troubles psychiques consécutifs à l'accident doit, en règle générale, être niée d'emblée, tandis qu'elle doit être admise en cas d'accident grave; pour admettre le rapport de causalité adéquate entre un accident de gravité moyenne et des troubles psychiques, il faut prendre en considération un certain nombre de critères (<ref-ruling>, 403).
En l'espèce, l'événement du 13 juillet 2004 peut être qualifié d'accident de gravité moyenne. Les circonstances dans lesquelles il est survenu ne sont ni dramatiques, ni impressionnantes. Les lésions physiques (douleurs au coude) n'étaient pas de nature, selon l'expérience, à entraîner des troubles psychiques. Elles n'ont pas empêché l'assuré travailler pendant plusieurs mois sans se plaindre. L'assuré a subi une longue incapacité de travail, ainsi que des douleurs persistantes pendant une longue durée, sans toutefois que l'on puisse les rattacher à un substrat organique. Il n'y a pas eu d'erreur dans le traitement médical. Dans ces conditions, les critères posés par la jurisprudence pour admettre le rapport de causalité adéquat entre l'événement du 13 juillet 2004 et les atteintes éventuelles à la santé psychique du recourant ne seraient pas remplis.
6. S'agissant d'un litige qui concerne des prestations d'assurance, la procédure est en principe gratuite (art. 134 OJ). Dans la mesure où elle vise à la dispense des frais de justice, la demande d'assistance judiciaire est dès lors sans objet. En revanche, les conditions auxquelles l'art. 152 al. 1 et 2 OJ subordonne la désignation d'un avocat d'office sont réalisées. Les conclusions du recours n'étaient pas d'emblée vouées à l'échec et, sur le vu des pièces produites, l'indigence du recourant est établie.
Le recourant est rendu attentif au fait qu'il devra rembourser la caisse du tribunal s'il devient ultérieurement en mesure de le faire (art. 152 al. 3 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Il n'est pas perçu de frais de justice.
3. L'assistance judiciaire est accordée. Les honoraires (y compris la taxe à la valeur ajoutée) de Maître Astyanax Peca sont fixés à 2500 fr. pour la procédure fédérale et seront supportés par la caisse du tribunal.
4. Le présent arrêt sera communiqué aux parties, au Tribunal cantonal des assurances sociales de la République et canton de Genève et à l'Office fédéral de la santé publique.
Lucerne, le 23 octobre 2007
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière: