Faits:
A. Le 7 juin 2005, D._, né en 1964, a annoncé à la Caisse nationale suisse d'assurance en cas d'accidents (ci-après : CNA) qu'il s'était blessé le gros orteil gauche alors qu'il travaillait sur un chantier pour l'entreprise X._.
Entendu par un inspecteur de la CNA, le 15 juin 2006, il a précisé qu'il avait commencé son activité pour X._ 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éritables douleurs sur le moment, il avait poursuivi son activité jusqu'à 17h30. Son contremaître l'avait ensuite véhiculé à son domicile, car il avait de la peine à marcher. Durant la nuit, il n'avait pas réussi à dormir en raison de douleurs dans le pied. Le lendemain à l'aube, il s'était rendu à l'Hôpital Y._, où une fracture de l'orteil avait été diagnostiquée. L'entreprise X._ avait refusé d'annoncer l'accident à la CNA, ne l'avait pas rémunéré pour sa journée de travail le 1er juin 2005 et l'avait licencié avec effet immédiat.
Le 28 août 2005, le docteur A._, médecin-assistant à l'Hôpital Y._, a exposé qu'il avait examiné D._ le 2 juin 2005 à 7h45. Le patient présentait une tuméfaction douloureuse de la 1ère phalange du 5ème orteil, qui était fracturée. Le docteur A._ a attesté une incapacité de travail totale du 2 au 16 juin 2005 (du 2 au 23 juin 2005, selon un certificat médical du 3 juin 2005) et a prescrit notamment le port de béquilles.
Entre-temps, la CNA s'est renseignée par téléphone auprès de l'entreprise X._, le 30 juin 2005. G._ a déclaré que D._ s'était présenté dans les bureaux de l'entreprise un après-midi vers 15h00, en prétendant avoir une formation de peintre. G._ l'avait invité à se présenter sur le chantier le lendemain «pour voir ce qu'il savait faire». D._ était arrivé en boitant et s'était vu confié la peinture d'un plafond, afin de montrer s'il savait peindre. Ce n'était pas le cas, de sorte qu'il avait été prié de quitter le chantier après une heure de travail environ. G._ avait été présent pendant tout ce temps et attestait formellement qu'aucun accident ne s'était produit. Il a confirmé ses déclarations, par lettre du 1er juillet 2005 à la CNA.
Cette dernière a invité D._ à citer un témoin de son activité pour X._ dans la journée du 1er juin 2005. A défaut de réponse de sa part, elle a réitéré cette invitation, en précisant qu'à défaut de collaboration, elle statuerait en l'état du dossier. Le 24 novembre 2005, D._ a proposé d'entendre comme témoins C._, apprenti-peintre, R._, contremaître, et L._, qui habitait à proximité du chantier sur lequel il avait travaillé.
R._ a déclaré qu'il n'avait «absolument aucun souvenir d'un certain D._». Il se rappelait d'un homme, soi-disant peintre, qui était resté très peu sur un chantier, mais en aucun cas il n'y avait eu un accident. Il ne souvenait pas de l'avoir ramené à la maison en fin de journée et n'avait jamais eu de contact avec cet homme. C._ ne connaissait pas D._ et n'avait plus travaillé avec R._ depuis Noël 2004. Enfin, L._ a déclaré qu'elle connaissait D._ et lui avait parlé un après-midi alors qu'il était occupé sur les façades d'un bâtiment à M._, 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 l'assuré n'étaient pas rendues suffisamment vraisemblables. D._ s'est opposé à cette décision en précisant qu'il connaissait R._ de longue date. Ce dernier, rencontré par hasard dans un café, lui avait exposé que son employeur cherchait à engager des peintres en bâtiment et lui avait suggéré de se présenter. Après un entretien avec G._ le 31 mai 2005, il avait été convenu qu'il commencerait le travail le lendemain. Le 1er juin 2005, il avait travaillé la journée avec trois apprentis, notamment à peindre des balcons et des plafonds. Il s'était blessé au pied entre 16h00 et 16h30, mais avait continué à travailler. En fin d'après-midi, R._ l'avait informé du fait que son employeur n'avait plus besoin de ses services. Il l'a ramené à la maison vers 17h30, comme il l'avait déjà fait pour la pause de midi. Par la suite, D._ a donné de nouvelle précisions relatives à sa journée de travail, en ne mentionnant toutefois plus avoir travaillé qu'avec un seul apprenti, sans pouvoir garantir qu'il s'agissait de C._.
Entendu à nouveau par la CNA, le 21 mars 2006, R._ a confirmé ses premières déclarations et a exclu de se soumettre à une confrontation avec D._. Le 6 juin 2006, G._ a lui aussi exclu une telle confrontation.
Par décision sur opposition du 12 juin 2006, la CNA a maintenu son refus d'allouer des prestations d'assurances.
B. D._ a déféré la cause au Tribunal des assurances du canton du Valais, en maintenant la version des faits alléguée pendant la procédure devant la CNA. Il a ajouté, d'une part, que sa fille aînée avait été confiée pendant près de deux ans à la garde de R._ et de son épouse, entre 1990 et 1992, et d'autre part, qu'il avait dirigé une entreprise - aujourd'hui en faillite - dans laquelle la fille de R._ avec fait un stage d'employée de commerce. R._ avait par ailleurs effectué quelques travaux pour D._, au restaurant W._. Afin de prouver ses allégations, le recourant a demandé l'audition comme témoins de G._, R._ et L._, ainsi que d'un apprenti dont le nom restait à préciser.
Par jugement du 13 novembre 2007, le Tribunal des assurances du canton du Valais a rejeté le recours, sans avoir entendu les témoins requis. Il a notamment considéré qu'il était peu vraisemblable que les témoins déjà entendus par la CNA reviennent sur leurs déclarations.
C. D._ interjette un recours contre ce jugement. Il en demande l'annulation et conclut au renvoi de la cause à la juridiction cantonale pour qu'elle entende les témoins cités et statue à nouveau. L'intimée conclut 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 recourant soutient que les premiers juges ont violé l'art. 61 let. c LPGA en niant son droit aux prestations de l'assurance-accidents sans entendre les témoins qu'il avait cités.
2. 2.1 Sous réserve de l'art. 1 al. 3 de la loi fédérale du 20 décembre 1968 sur la procédure administrative, la procédure devant le tribunal cantonal des assurances est réglée par le droit cantonal. Elle doit toutefois satisfaire à certaines exigences de droit fédéral. En particulier, le tribunal cantonal doit établir les faits déterminants pour la solution du litige, avec la collaboration des parties. Il administre les preuves nécessaires et les apprécie librement (art. 61 let. c LPGA). Cette disposition exprime le principe inquisitoire, qui s'appliquait déjà avant l'entrée en vigueur de l'art. 61 let. c LPGA dans le domaine des assurances sociales et qui impose au juge de constater d'office les faits pertinents de la cause, après avoir administré les preuves nécessaires (cf. <ref-ruling> consid. 2 p. 195).
2.2 Le tribunal peut considérer qu'un fait est prouvé et renoncer à de plus amples mesures d'instruction lorsqu'au terme d'un examen objectif, il ne conçoit plus de doutes sérieux sur l'existence de ce fait (cf. <ref-ruling> consid. 3.2, p. 324; SVR 2007 IV no 31 p. 111 [I 455/06], consid. 4.1). Si de tels doutes subsistent, il lui appartient de compléter l'instruction de la cause, pour autant que l'on puisse attendre un résultat probant des mesures d'instruction entrant raisonnablement en considération. Le cas échéant, il peut renoncer à l'administration d'une preuve s'il acquiert la conviction, au terme d'une appréciation anticipée des preuves, qu'une telle mesure ne pourrait l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 429; <ref-ruling> consid. 6c/cc in fine p. 135).
2.3 Saisi d'un recours en matière de droit public, le Tribunal fédéral ne peut, en principe, revoir le résultat de l'appréciation anticipée des preuves - et en conclure à une violation de la maxime inquisitoire - , qu'en cas d'inexactitude manifeste (art. 97 al. 1 et 105 al. 1 et 2 LTF; cf. également Meyer in : M. A. Niggli, P. Uebersax, H. Wiprächtiger [édit.], Bundesgerichtsgesetz, Bâle 2008, n. 34a, 60 et note 170 ad art. 105). Il en va toutefois différemment dans les litiges portant, comme dans le cas présent, sur l'octroi ou le refus de prestations en espèces de l'assurance-accidents ou de l'assurance militaire, dans lesquels le Tribunal fédéral n'est pas lié par les faits constatés par l'autorité précédente (art. 97 al. 2 et 105 al. 3 LTF).
3. 3.1 En l'occurrence, il n'est pas litigieux que le recourant a travaillé au moins une heure pour l'entreprise X._ le matin du 1er juin 2005. Il est également établi qu'il s'est présenté le lendemain, 2 juin 2005, à l'Hôpital Y._, où une fracture de la 1ère phalange du 5ème orteil du pied droit a été constatée. Il est quasiment exclu que cette lésion se soit produite sans influence d'un facteur extérieur, de sorte qu'il faut en tout cas conclure à l'existence d'une lésion assimilée à un accident au sens de l'<ref-law> (en relation avec l'<ref-law>). Reste à déterminer si cette lésion s'est produite alors que le recourant était couvert par l'intimée contre le risque d'accident.
3.2 D'après l'<ref-law>, l'assurance produit ses effets dès le jour où le travailleur commence ou aurait dû commencer le travail en vertu de l'engagement, mais en tout cas dès le moment où il prend le chemin pour se rendre au travail. Elle cesse de produire ses effets à l'expiration du trentième jour qui suit celui où a pris fin le droit au demi-salaire au moins (<ref-law>). Sont couverts les accidents professionnels et non professionnels (<ref-law>).
En l'occurrence, il s'ensuit que l'intimée ne peut exclure la couverture d'assurance que si les lésions constatées par le docteur A._ sont survenues, au plus tard, le 31 mai 2005 jusqu'à minuit.
En l'occurrence, il s'ensuit que l'intimée ne peut exclure la couverture d'assurance que si les lésions constatées par le docteur A._ sont survenues, au plus tard, le 31 mai 2005 jusqu'à minuit.
3.3 3.3.1 Les premiers juges ont motivé le rejet du recours de l'assuré en se fondant, pour l'essentiel, sur les déclarations de G._, d'après lesquelles l'assuré s'est présenté au travail en boitant, le 1er juin 2005, et sur le fait que l'assuré n'a pu citer aucun témoin de l'accident allégué. Par ailleurs, sa description de sa journée de travail était contredite par G._ et R._. Ses déclarations n'étaient donc pas suffisamment probantes pour établir qu'il s'était blessé le 1er juin 2005, et non la veille. Le seul fait qu'elles fussent étayées par le témoignage de L._ - en tout cas sur le fait qu'il avait travaillé l'après-midi du 1er juin 2005 à repeindre les façades d'un bâtiment -, n'était pas suffisant. Par ailleurs, il n'était pas nécessaire d'entendre comme témoins G._ et R._, dès lors qu'il était peu vraisemblable qu'ils reviennent sur leurs déclarations.
3.3.2 Cette appréciation anticipée des preuves ne peut être suivie. En l'espèce, les déclarations des différents protagonistes sont à ce point contradictoires que certaines sont forcément contraires à la réalité. Sans qu'il soit utile, à ce stade de la procédure, de procéder à une appréciation plus complète des preuves, on relèvera que les allégations du recourant sont, pour l'essentiel, restées constantes, qu'elles sont relativement détaillées et en partie corroborées par le témoignage de L._. Par ailleurs, on peut effectivement s'étonner que l'employeur ait confié des travaux de peinture d'un plafond au recourant, le 1er jour de travail, si celui-ci s'est effectivement présenté en boitant. En d'autres termes, les allégations du recourant ne sont pas à ce point dépourvues de vraisemblance qu'on puisse se dispenser d'entendre les témoins cités. Il n'est pas exclu qu'entendus par un tribunal, pour certains sous serment, sous menace de sanctions pénales, le recourant ou l'un des témoins cités revienne en tout ou partie sur ses déclarations. Cela vaut d'autant plus que certains détails cités par le recourant - relatifs au fait qu'il connaissait bien R._, contrairement aux déclarations de ce dernier - sont probablement vérifiables, éventuellement par l'audition d'autres témoins. Si elles sont confirmées, ou au contraire infirmées, ces précisions sont de nature à accréditer ou contredire en partie les autres allégations du recourant, en faveur ou au détriment de la version des faits présentée par l'employeur. Enfin, dans un cas où l'établissement des faits prête à discussion et dépend largement de la preuve testimoniale, il est important que la juridiction cantonale porte une appréciation directe sur un témoignage, selon les formes prescrites par la procédure cantonale, plutôt que de se limiter au procès-verbal d'audition dressé par l'intimée en procédure administrative (cf. arrêts du Tribunal fédéral des assurances C 206/00 du 17 novembre 2000, C 362/96 du 26 mars 1998 et U 90/93 du 12 novembre 1993).
4. Vu ce qui précède, les premiers juges ne pouvaient nier le droit aux prestations litigieuses sans compléter l'instruction et entendre au moins les témoins cités par le recourant. La cause leur sera par conséquent retournée à cet effet.
Le recourant obtient gain de cause et n'a donc pas à supporter de frais de justice (<ref-law>); il peut, par ailleurs, prétendre une indemnité de dépens à la charge de l'intimée (art. 68 al. 1 et 2 LTF). Sa demande d'assistance judiciaire est donc sans objet. L'intimée supportera par ailleurs les frais de justice (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et le jugement du Tribunal des assurances du canton du Valais du 13 novembre 2007 est annulé. La cause est renvoyée à la juridiction de première instance pour complément d'instruction au sens des considérants et nouveau jugement.
2. Les frais de justice, arrêtés à 500 fr., sont mis à la charge de l'intimée.
3. L'intimée versera au recourant la somme de 2500 fr. à titre de dépens pour la dernière instance.
4. Le présent arrêt est communiqué aux parties, au Tribunal des assurances du canton du Valais et à l'Office fédéral de la santé publique.
Lucerne, le 14 avril 2008
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral