Faits : A. A._ a travaillé en qualité de sableur et peintre en bâtiment pour la société B._ Sàrl à compter du 10 mars 2008. Il était, à ce titre, assuré obligatoirement contre le risque d'accident et de maladie professionnelle auprès de la Caisse nationale suisse d'assurance en cas d'accidents (CNA). Durant le premier semestre de l'année 2011, il a subi plusieurs périodes d'incapacité totale ou partielle de travail en raison de douleurs à un bras. A partir du 22 août 2011, il s'est trouvé en incapacité totale de travail. Entre-temps, son contrat de travail avait été résilié avec effet au 31 octobre 2011. L'assuré a subi deux interventions chirurgicales (neurolyses) au niveau du coude droit, destinées à traiter une neuropathie de compression des nerfs radial et ulnaire, les 25 août 2011 et 12 janvier 2012. Le 25 janvier 2013, il a transmis à la CNA une déclaration de sinistre LAA faisant état d'une suspicion de maladie professionnelle en relation avec une inflammation touchant son bras droit. Par décision du 23 mai 2013, la CNA a dénié à l'assuré le droit à des prestations d'assurance, motif pris que les troubles annoncés ne relevaient pas d'une maladie professionnelle. Saisie d'une opposition, elle a procédé, le 27 août 2013, à une appréciation du poste de travail de l'assuré sur un chantier, où sa manière de travailler a été présentée par un collègue. La CNA a requis ensuite l'avis du docteur C._, spécialiste en chirurgie et membre de sa division de médecine des assurances. Dans son rapport du 30 mai 2014, ce médecin a posé les diagnostics suivants: - neuropathie compressive de la branche profonde du nerf radial au niveau du coude droit ou syndrome du supinateur; - neuropathie compressive du nerf ulnaire au niveau du coude droit; - épicondylopathie radiale du coude gauche; - périarthrose numéro-scapulaire de l'épaule droite; - syndrome du défilé thoracique; - cervicobrachialgies sur discopathie C5/6 et hernie discale foraminale C6/7 avec compression de la racine nerveuse C7 droite. Il a conclu qu'aucun des différents tableaux cliniques n'était consécutif, de manière prépondérante ou nettement prépondérante, à l'activité professionnelle de l'assuré, et que son travail n'avait joué qu'un rôle de facteur déclencheur des troubles. Par décision du 22 septembre 2014, la CNA a rejeté l'opposition. B. Par jugement du 6 janvier 2016, la Cour des assurances sociales du Tribunal cantonal du Valais a rejeté le recours formé par l'assuré contre la décision sur opposition du 22 septembre 2014. C. A._ forme 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, au renvoi de la cause à l'autorité précédente pour qu'elle mette en oeuvre une expertise médicale tendant à déterminer le lien de causalité entre ses troubles et l'activité de sableur. Par ailleurs, il requiert le bénéfice de l'assistance judiciaire. La CNA conclut au rejet du recours. La cour cantonale et l'Office fédéral de la santé publique ont renoncé à se déterminer.