Faits:
A. A.a S._ a annoncé à la Caisse nationale suisse d'assurance en cas d'accidents (CNA) qu'il s'était blessé le gros orteil gauche alors qu'il travaillait sur un chantier pour l'entreprise X._ Sàrl, à Y._, le 1er juin 2005. Il s'est rendu, le lendemain, à l'hôpital de Y._, où les examens radiologiques ont révélé une fracture de la 1ère phalange du 5ème orteil gauche. Le docteur A._ a établi un certificat d'incapacité de travail pour la période du 2 au 26 juin 2005. Ce document a été remis à la CNA, par l'intermédiaire des Syndicats chrétiens interprofessionnels de Y._, le 7 juin 2005. Les radiographies ne sont parvenues qu'ensuite à l'assurance-accidents, après un entretien téléphonique avec le service de radiologie de l'hôpital, le 30 juin 2005.
Entendu par un inspecteur de la CNA, le 15 juin 2005, S._ a précisé qu'il avait commencé son activité pour X._ Sàrl le 1er juin 2005, à 6h45. Il avait été engagé oralement, comme peintre, pour une durée indéterminée, avec un temps d'essai d'un mois. Vers 16h00, alors qu'il se trouvait sur le 1er étage d'un échafaudage, une échelle en bois lui avait glissé des mains et lui était tombée sur le pied. En l'absence de véritable douleur sur le moment, il avait poursuivi son activité jusqu'à 17h30. Son contremaître, M._, l'avait ensuite véhiculé à son domicile, car il avait de la peine à marcher.
Le 30 juin 2005, la CNA s'est renseignée par téléphone auprès de l'entreprise X._ Sàrl. R._ a déclaré que S._ s'était présenté en boitant sur le chantier pour un essai de travail, alléguant être au bénéfice d'une formation de peintre et d'une expérience de dix ans dans ce domaine. Renvoyé en raison de son manque de connaissances professionnelles, il n'était resté qu'une heure sur le chantier, sans subir le moindre accident. R._ a précisé avoir toujours été présent à l'endroit où oeuvrait le recourant. Il a confirmé cette version des faits par un courrier à la CNA, le 1er juillet 2005.
Cette dernière a invité S._ à citer un témoin de son activité pour X._ Sàrl, dans la journée du 1er juin 2005. Il a proposé d'entendre C._, apprenti-peintre, M._, et L._, qui habitait à proximité du chantier sur lequel il avait travaillé.
Le 29 novembre 2005, M._ a déclaré à la CNA qu'il n'avait « absolument aucun souvenir d'un certain S._ ». Il se rappelait d'un homme, soit disant peintre, qui était resté très peu sur un chantier, mais en aucun cas il n'y avait eu un accident. Il ne se souvenait pas l'avoir ramené à la maison en fin de journée et n'avait jamais eu de contact avec cet homme. C._, pour sa part, ne connaissait pas S._ et n'avait plus travaillé avec M._ depuis la fin de l'année 2004. Enfin, L._ a déclaré qu'elle connaissait S._ et lui avait parlé un après-midi alors qu'il était occupé sur les façades d'un bâtiment à Y._, en face du numéro 9 de la rue Z._, où elle habitait.
Par décision du 6 décembre 2005, la CNA a refusé d'allouer des prestations, au motif que les allégations de S._ n'étaient pas rendues suffisamment vraisemblables. Celui-ci s'est opposé à ce refus en mentionnant avoir travaillé avoir trois apprentis, le 1er juin 2005. Il a par ailleurs allégué que M._ lui avait lui-même suggéré de se présenter à son employeur, qui cherchait des peintres en bâtiment. Le 13 janvier 2006, le mandataire de S._ a complété l'opposition en indiquant qu'un apprenti lui avait remis une échelle laissée sur l'échafaudage devant l'immeuble, que celle-ci lui avait glissé des mains et qu'elle était tombée sur son pied gauche. Il n'a plus fait mention de la présence d'autres apprentis.
Entendu à nouveau par la CNA le 21 mars 2006, M._ a maintenu sa version des faits et a exclu de se soumettre à une confrontation avec S._, qui l'avait par ailleurs harcelé jusqu'à son domicile pour lui demander des explications. Le 6 juin 2006, R._ a lui aussi exclu une confrontation.
Par décision sur opposition du 12 juin 2006, la CNA a maintenu son refus d'allouer des prestations.
B. B.a S._ a déféré la cause au Tribunal cantonal valaisan et demandé l'audition, comme témoins, de R._, M._ et L._, ainsi que d'un apprenti dont le nom restait à préciser.
Par jugement du 13 novembre 2007, le Tribunal cantonal valaisan a rejeté le recours sans entendre les témoins requis. Le Tribunal fédéral a toutefois annulé ce jugement et renvoyé la cause à la juridiction cantonale pour qu'elle administre les preuves testimoniales proposées par le recourant et statue à nouveau (arrêt 8C_831/2007 du 14 avril 2008).
B.b Le Tribunal cantonal valaisan a procédé au complément d'instruction requis. Il a entendu divers témoins, les 4 novembre 2008 et 3 mars 2009.
R._ a déclaré qu'il ne connaissait pas S._, qui n'avait jamais travaillé pour X._ Sàrl. Il était possible qu'il se soit présenté aux bureaux de l'entreprise pour demander du travail, mais il ne l'avait jamais vu personnellement. En tout les cas, S._ n'avait pas pu peindre un bout de plafond s'il s'était présenté en boitant.
L._ a déclaré qu'elle connaissait S._, qui était un ami. Elle l'avait vu sur un chantier en face de son domicile, rue Z._, occupé à des travaux de peinture, un bidon à la main, sans pouvoir préciser la date. Par la suite, celui-ci lui avait expliqué avoir été victime d'un accident sur le chantier en question; il avait notamment déclaré qu'il avait reçu un bidon sur le pied.
M._ a exposé qu'il connaissait S._ de vue et qu'il avait gardé sa fille dans les années 1990/1992, avec son épouse. Il n'avait plus eu de contact avec lui depuis 2004, et, en particulier, ne l'avait pas mis en relation avec son employeur. Il ne se souvenait pas avoir déclaré à la CNA que le prénommé l'avait harcelé.
Le Tribunal cantonal a complété l'instruction en faisant produire le dossier constitué par l'assurance-invalidité à la suite d'une demande de prestations de S._. Par jugement du 17 août 2009, il a rejeté le recours interjeté par ce dernier dans la cause l'opposant à la CNA. Il n'a pas alloué de dépens au recourant en raison du rejet de ses conclusions et a déclaré la procédure gratuite.
C. S._ interjette un recours en matière de droit public contre ce jugement. En substance, il en demande la réforme en ce sens que la CNA soit condamnée à lui allouer des prestations pour toute la durée de l'incapacité de travail liée à l'accident du 1er juin 2005 et qu'une indemnité lui soit allouée pour ses frais et dépens en instance cantonale, au titre de l'assistance judiciaire. Il demande également l'assistance judiciaire pour la procédure devant le Tribunal fédéral.
L'intimée 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. 1.1 Le Tribunal fédéral est en principe lié par les faits constatés par les premiers juges (art. 105 al. 1 LTF), à moins qu'ils aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF. Le Tribunal fédéral peut alors rectifier ou compléter les faits d'office (art. 105 al. 2 LTF). La partie recourante peut également contester des constatations de faits ainsi irrégulières si la correction du vice peut influer sur le sort de la cause (art. 97 al. 1 LTF).
1.2 Par exception à cette règle générale, si la décision qui fait l'objet d'un recours concerne l'octroi ou le refus de prestations en espèces de l'assurance-accidents ou de l'assurance militaire, le recours peut porter sur toute constatation incomplète ou erronée des faits (art. 97 al. 2 LTF). Le Tribunal fédéral n'est pas lié par les faits établis par l'autorité précédente (art. 105 al. 3 LTF).
1.3 Dans un arrêt du 11 septembre 2009 (<ref-ruling>), le Tribunal fédéral a considéré que l'exception prévue par les art. 97 al. 2 et 105 al. 3 LTF ne s'applique pas lorsque l'existence même d'une couverture d'assurance au moment de l'accident est litigieuse. Il n'est pas déterminant que l'octroi de prestations en espèces de l'assurance-accidents dépende de l'issue du litige relatif à la condition d'assurance.
En l'occurrence, les premiers juges ont nié que l'assuré fût au bénéfice d'une couverture d'assurance auprès de l'intimée lorsqu'il s'est blessé au pied gauche. Il s'ensuit que le pouvoir d'examen du Tribunal fédéral dans la présente procédure se limite, en ce qui concerne les faits, aux constatations manifestement inexacte ou établies en violation du droit par les premiers juges.
2. 2.1 Le recourant a allégué, en instance cantonale, qu'il avait subi un accident sur un chantier, rue Z._ à Y._, alors qu'il travaillait pour l'entreprise X._ Sàrl. Il reproche aux premiers juges de n'avoir pas tenu cette version des faits pour établie et met en évidence les imprécisions et les contradictions des témoignages de R._ et M._. Il se réfère en outre au témoignage de L._.
2.2 Il est exact que chacun des deux principaux témoins, R._ et M._, a modifié sa version des faits entre le moment où il a été entendu par la CNA et son audition par les premiers juges. Dans un premier temps, R._ a déclaré que le recourant avait travaillé une heure en sa présence, à l'essai, avant d'exposer aux premiers juges qu'il ne le connaissait pas et ne l'avait jamais vu personnellement. M._ a déclaré pour sa part à la CNA qu'il ne connaissait pas le recourant, avant d'admettre devant les premiers juges qu'il le connaissait, mais n'avait plus de contact avec lui depuis 2004. Il n'en reste pas moins que ces deux témoins ont fermement nié, depuis le début, que le recourant ait été victime de l'accident de travail qu'il allègue, le 1er juin 2005. Aucun autre témoin n'a pu le confirmer et le recourant n'a pu citer le nom de l'apprenti avec lequel il aurait travaillé. L._ n'a pu que confirmer avoir vu une fois le recourant travailler sur le chantier de la rue Z._, sans en préciser la date, même approximativement. Concernant la survenance d'un accident, elle n'a pu que rapporter les propos du recourant : celui-ci lui avait déclaré avoir reçu un bidon de peinture sur le pied, ce qui contredit ses allégations relatives à une échelle tombée sur son pied. Dans ces conditions, les premiers juges pouvaient considérer, sans arbitraire, qu'il n'était pas possible d'établir si le recourant avait ou non subi l'accident allégué, le 1er juin 2005, après avoir commencé à travailler pour l'entreprise X._ Sàrl. Sur ce point, le recours est mal fondé.
3. Le recourant fait encore grief à la juridiction cantonale de n'avoir pas statué sur la prise en charge de ses frais de défense, par l'Etat, au titre de l'assistance judiciaire. Il n'expose toutefois pas quelle règle de droit fédéral les premiers juges auraient violée, ni en quoi ils auraient appliqué arbitrairement une règle de procédure cantonale. Sur ce point, la seule mention d'une violation « du droit de procédure, à savoir l'obligation de statuer sur toute requête faite », ne constitue pas une motivation suffisante. Le seul fait que les premiers juges n'ont pas statué, directement dans le jugement au fond, sur le droit à une indemnité au titre de l'assistance judiciaire, ne permet pas de conclure à un déni de justice formel ou matériel. Le grief est donc mal fondé dans la mesure où il est recevable.
4. Vu le sort de ses conclusions, le recourant ne peut prétendre de dépens (art. 68 al. 1 LTF). La procédure est onéreuse et les frais de justice sont mis à sa charge (art. 66 al. 1 LTF). Les conditions auxquelles l'art. 64 al. 1 et 2 LTF soumet l'octroi de l'assistance judiciaire sont toutefois remplies, de sorte que le recourant est provisoirement dispensé de s'acquitter des frais judiciaires, les honoraires de son mandataire étant pris en charge par la caisse du Tribunal. Le recourant est rendu attentif au fait qu'il devra rembourser l'aide reçue s'il devient en mesure de le faire ultérieurement (art. 64 al. 4 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. L'assistance judiciaire est accordée au recourant.
3. Les frais judiciaires, arrêtés à 750 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4. Daniel Cipolla est désigné en tant qu'avocat d'office du recourant et une indemnité de 1'800 fr. lui est allouée à titre d'honoraire, supportée par la caisse du Tribunal.
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 5 août 2010
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral