Faits: A. A.a. Z._, né en 1957, travaillait depuis le 1 er juin 1983 au service de X._ SA en qualité de collaborateur de production. A ce titre, il était assuré contre les accidents et les maladies professionnelles par la Caisse nationale suisse d'assurance en cas d'accidents (CNA). En raison de troubles respiratoires apparus dans le courant du mois d'avril 2006, Z._ a été en incapacité de travail depuis le 12 juin 2006. Soupçonnant l'existence d'une maladie professionnelle, l'employeur de Z._ a annoncé le cas à la CNA le 27 septembre 2006. Le 29 janvier 2007, le docteur C._, spécialiste FMH en médecine du travail et en médecine générale et médecin-conseil de la CNA, a indiqué que les tentatives de reprise du travail dans un autre secteur, sans exposition à des produits chimiques, avaient échoué, les problèmes respiratoires étant réapparus. Seul un arrêt total du travail avait permis une amélioration de l'état de santé de l'intéressé. Dans ses conclusions, le médecin signalait qu'il n'était pas possible d'identifier un facteur professionnel précis à l'origine des troubles respiratoires de type asthmatique présentés par l'assuré. La disparition des symptômes en dehors du travail forçait à admettre l'existence d'un facteur professionnel non identifié et de conclure à une maladie professionnelle. La capacité de travail était cependant incontestablement entière en dehors du site chimique de Y._. Par décision du 26 février 2007, la CNA a déclaré Z._ inapte à toute activité dans un site de production de l'industrie chimique. Le lendemain, l'assuré a été licencié avec effet au 31 août 2007. La CNA a versé à l'intéressé une indemnité journalière de transition à partir du 1 er mars 2007, pour une durée de quatre mois. Z._ n'a pas repris d'activité lucrative en raison d'une réapparition de ses troubles respiratoires (voir attestation de son médecin traitant, le docteur A._, du 20 avril 2007). Le docteur C._ a relevé que la réapparition de la même symptomatologie en dehors du site chimique de Y._ remettait en question l'existence d'une maladie professionnelle. Il a souligné que cette dernière avait été admise dans un contexte peu clair, essentiellement en raison de la disparition des symptômes à l'arrêt de travail. Dans son rapport d'expertise du 26 août 2008 mandaté par la CNA, le docteur K._, médecin auprès de l'Institut V._, a constaté que le dossier soulevait de nombreuses questions sans réponses malgré les investigations effectuées. Aucun élément au dossier ne permettait d'établir un lien formel entre les symptômes et l'activité professionnelle. Tout au plus, l'environnement professionnel avait-il pu aggraver ou maintenir transitoirement une hyper-réactivité bronchique ou un asthme après une infection initiale des bronches en avril 2006. Z._ a quitté définitivement la Suisse le 1 er mai 2008 pour s'installer avec sa famille au Maroc. Par décision du 18 septembre 2008, la CNA a révoqué sa prise en charge initiale, motif pris qu'aucune des conditions requises pour l'octroi de prestations n'était remplie. A.b. L'assuré a formé opposition à cette décision en demandant la mise en oeuvre d'une nouvelle expertise médicale. La CNA a confié la réalisation d'une nouvelle expertise au Service de pneumologie de l'Hôpital N._. Dans leur rapport du 11 mars 2010, le professeur J._, médecin adjoint agrégé et le docteur G._, médecin interne, ont posé les diagnostics d'asthme bronchique avec facteurs déclenchants climatiques et possiblement psychiques, emphysème pulmonaire scannographique, syndrome obstructif de degré léger, apparemment non réversible, compatible avec une BPCO ou un asthme insuffisamment contrôlé, voire fixé. Selon ces médecins, la récidive de symptômes respiratoires identiques en dehors de tout contexte professionnel montrait que l'asthme n'était pas lié exclusivement à l'environnement professionnel. Une maladie professionnelle n'étant plus retenue, la décision d'inaptitude ne se justifiait plus. Dans une appréciation médicale du 28 septembre 2010, le docteur O._, spécialiste FMH en médecine du travail et en médecine générale auprès de la division médecine du travail de la CNA, a indiqué que le diagnostic d'asthme bronchique n' était pas contesté par les experts et que cette maladie était toujours présente. L' asthme n'était pas lié exclusivement à l'environnement professionnel mais des facteurs déclenchants climatiques et possiblement psychiques jouaient un rôle. L'assuré présentait toujours des symptômes asthmatiques en fonction des conditions climatiques, notamment lorsqu'il était soumis à des polluants atmosphériques. On pouvait ainsi s'attendre, en cas d'exposition à des produits chimiques, au développement de la même symptomatologie respiratoire qu'en 2006, de sorte qu'il était nécessaire de maintenir la décision d'inaptitude pour toute activité dans l'industrie chimique. Par décision du 12 août 2011, confirmée sur opposition le 3 février 2012, la CNA a annulé sa décision du 18 septembre 2008 au motif qu'elle était devenue sans objet et reconnu le droit aux prestations d'assurance jusqu'au 30 avril 2008. Par ailleurs, elle a constaté que la décision d'inaptitude du 26 février 2007 ne pouvait pas être révoquée mais qu'elle ne débouchait sur l'octroi d'aucune indemnité pour changement d'occupation, au motif que l'assuré avait transféré son domicile dans un pays non membre de l'Union européenne à compter du 1 er mai 2008. B. Z._ a recouru contre cette décision. Statuant le 7 mai 2013, la Cour des assurances sociales du Tribunal cantonal valaisan a rejeté le recours. Elle a refusé de lui allouer une indemnité pour changement d'occupation dès lors qu'il ne remplissait pas la condition du domicile en Suisse. Par ailleurs, elle a nié le droit à d'autres prestations de l'assurance-accidents (prise en charge du traitement médical et indemnités journalières) au-delà du 30 avril 2008, au motif qu'à partir de cette date, les symptômes de la maladie professionnelle avaient disparu. C. Z._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, en concluant à l'octroi d'une indemnité pour changement d'occupation pour la période du 1 er juillet 2007 au 30 juin 2011, soit un montant de 345'723 fr. 85, déduction faite de l'acompte déjà reçu de 57'455 fr. 15, plus intérêts à 5 % l'an dès le 1 er juillet 2011. Il sollicite en outre le bénéfice de l'assistance judiciaire. La CNA conclut au rejet du recours tandis que l'Office fédéral de la santé publique a renoncé à se déterminer. 