Faits :
A.
Par jugement du 22 novembre 2017, le Tribunal du IIème arrondissement pour le district de Sion a reconnu A._ coupable d'actes d'ordre sexuel avec des enfants et de viol commis au préjudice de B._ et l'a condamné à 36 mois de peine privative de liberté, avec sursis partiel portant sur 18 mois durant 3 ans. A._ a été condamné à verser à B._ une indemnité de 18'000 fr. en réparation du tort moral subi.
Statuant sur appel de A._ et appel joint du ministère public, la Cour pénale II du Tribunal cantonal valaisan les a rejetés par jugement du 3 mars 2020 et a confirmé en substance le jugement de première instance. La cour cantonale a toutefois constaté que B._ avait renoncé à sa qualité de partie plaignante par courriels des 12 et 19 décembre 2019, ainsi qu'au versement de l'indemnité en réparation du tort moral.
Le recours en matière pénale formé par A._ contre le jugement cantonal a été déclaré irrecevable par le Tribunal fédéral, par arrêt du 1er mai 2020 (6B_409/2020).
B.
Le 19 juin 2020, A._ a déposé une requête en révision du jugement du 3 mars 2020, à l'appui d'un courriel du 13 mai 2020, confirmé par courrier du lendemain, dans lequel B._ revenait sur ses déclarations en procédure.
Par ordonnance du 21 septembre 2020, la Cour pénale I du Tribunal cantonal valaisan, statuant par Juge unique, a refusé d'entrer en matière sur la demande de révision du jugement du 3 mars 2020.
C.
A._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'ordonnance du 21 septembre 2020 et conclut, avec suite de frais et dépens, à son annulation et au renvoi de la cause à la cour cantonale pour nouveau jugement. Subsidiairement, il conclut à son acquittement et à l'octroi d'une indemnité de 10'000 fr. au sens de l'art. 429 al. 1 let. c CPP. Il sollicite en outre l'octroi de l'assistance judiciaire et requiert l'effet suspensif.
La demande d'effet suspensif a été rejetée par le Président de la Cour de droit pénal le 20 octobre 2020.
D.
Invités à se déterminer sur le mémoire de recours, le ministère public s'est rallié aux considérants de l'ordonnance entreprise et a conclu au rejet du recours. La cour cantonale a déposé des observations et s'est référée à la décision entreprise, tout en se prévalant de dispositions cantonales s'agissant de la composition de la juridiction d'appel. Les observations ont été communiquées au recourant, lequel n'a pas répliqué.

Considérant en droit :
1.
Le recourant invoque une violation des art. 412 et 413 CPP et considère que sa demande en révision ne pouvait être déclarée irrecevable. Il se plaint également d'une composition irrégulière de la juridiction d'appel. Selon lui, le Juge unique a rendu l'ordonnance entreprise en violation des art. 21 et 412 CPP et des dispositions cantonales de procédure pénale et d'organisation judiciaire topiques.
1.1. L'<ref-law> permet à toute personne lésée par un jugement entré en force d'en demander la révision s'il existe des faits ou des moyens de preuve qui étaient inconnus de l'autorité inférieure et qui sont de nature à motiver l'acquittement ou une condamnation sensiblement moins sévère du condamné. Les faits ou moyens de preuve invoqués doivent ainsi être nouveaux et sérieux. Les faits ou moyens de preuve sont inconnus lorsque le juge n'en a pas eu connaissance au moment où il s'est prononcé, c'est-à-dire lorsqu'ils ne lui ont pas été soumis sous quelque forme que ce soit (cf. <ref-ruling> consid. 5.1.2). Ils sont sérieux lorsqu'ils sont propres à ébranler les constatations de fait sur lesquelles se fonde la condamnation et que l'état de fait ainsi modifié rend possible un jugement sensiblement plus favorable au condamné (<ref-ruling> consid. 1.1; <ref-ruling> consid. 5.1.4).
La procédure du rescindant instituée par le CPP se déroule, en principe, en deux phases, à savoir un examen préalable de la recevabilité (art. 412 al. 1 et 2 CPP) et un examen des motifs invoqués (art. 412 al. 3 et 4 et 413 CPP). Il s'agit de deux étapes d'une seule et même procédure, pour laquelle la juridiction d'appel est compétente (art. 412 al. 1 et 3 CPP).
Selon l'<ref-law>, la juridiction d'appel n'entre pas en matière sur la demande de révision si celle-ci est manifestement irrecevable ou non motivée ou si une demande de révision invoquant les mêmes motifs a déjà été rejetée par le passé. La procédure de non-entrée en matière selon cette disposition est en principe réservée à des vices de nature formelle (par exemple le défaut de qualité pour recourir, le caractère non définitif du jugement entrepris, etc.). Il est néanmoins loisible à la juridiction d'appel de refuser d'entrer en matière si les motifs de révision invoqués apparaissent d'emblée non vraisemblables ou mal fondés (<ref-ruling> consid. 3.5; arrêts 6B_742/2020 du 19 novembre 2020 consid. 1.2; 6B_813/2020 du 22 juillet 2020 consid. 1.1), ou encore lorsque la demande de révision apparaît abusive (arrêt 6B_813/2020 précité consid. 1.1 et les références citées).
Le refus d'entrer en matière s'impose alors pour des motifs d'économie de procédure, car si la situation est évidente, il n'y a pas de raison que l'autorité requière des déterminations (<ref-law>) pour ensuite rejeter la demande (<ref-law>; arrêts 6B_1110/2019 du 18 décembre 2019 consid. 1.1.2; 6B_324/2019 du 24 avril 2019 consid. 3.1 et les références citées).
Si la juridiction d'appel constate que les motifs de révision ne sont pas fondés, elle rejette la demande de révision et annule les éventuelles mesures provisoires (<ref-law>).
1.2. L'examen du motif de révision incombe à la "juridiction d'appel" selon les art. 412 et 413 CPP. A teneur de l'<ref-law>, la juridiction d'appel statue sur les demandes de révision. Selon l'al. 3, les membres de la juridiction d'appel ne peuvent pas statuer en révision dans la même affaire (cf. arrêt 6B_1114/2017 du 7 décembre 2017 consid. 2 sur ce point).
A teneur de l'<ref-law>, la Confédération et les cantons désignent leurs autorités pénales et en arrêtent la dénomination. Selon l'al. 2, ils fixent les modalités d'élection des membres des autorités pénales, ainsi que la composition, l'organisation et les attributions de ces autorités, à moins que ces questions soient réglées exhaustivement par le présent code ou d'autres lois fédérales.
L'autorité est valablement constituée lorsqu'elle siège dans une composition qui correspond à ce que le droit d'organisation judiciaire ou de procédure prévoit. Dans le cas contraire, elle commet un déni de justice formel. Si la composition de l'autorité est prévue par le droit cantonal, le Tribunal fédéral ne revoit l'interprétation et l'application de celui-ci que sous l'angle restreint de l'arbitraire (<ref-ruling> consid. 3.2; arrêt 1C_678/2017 du 5 avril 2018 consid. 2.1, publié in PJA 2018 760 et RDAF 2018 I 613, en lien avec les art. 29 et 30 Cst.; cf. <ref-ruling> consid. 4.5 sur la liberté laissée au législateur cantonal de choisir la composition du tribunal lorsque celui-ci est amené à connaître des cas d'irrecevabilité).
1.3. Le 23 juin 2020, le Juge cantonal a adressé un exemplaire de la demande de révision déposée par le recourant au ministère public et lui a imparti un délai pour se déterminer sur celle-ci. Par décision du même jour, il a accordé l'effet suspensif à la procédure de révision.
Dans l'ordonnance entreprise, le Juge cantonal a constaté que la condamnation du recourant ne reposait pas uniquement sur les déclarations de B._, mais bien plutôt sur un faisceau d'indices convergents, dont faisaient partie les affirmations de la jeune fille, lesquelles avaient été jugées crédibles. Dans un deuxième temps, le Juge cantonal a examiné la crédibilité de la rétractation de la jeune fille, telle qu'elle ressortait de son courrier de mai 2020. Il a considéré que celle-ci n'était pas d'une crédibilité suffisante pour ébranler les constatations sur lesquelles se fonde la condamnation du recourant. Pour ces motifs, il n'est pas entré en matière sur la demande de révision.
1.4. Ainsi que le relève le recourant, les conditions pour refuser d'entrer en matière sur la demande de révision ne sont pas réalisées en l'espèce. La requête en révision du jugement en condamnation pour actes d'ordre sexuel avec des enfants et viol commis au préjudice de B._ a été déposée à l'appui d'un courrier dans lequel cette dernière revenait sur ses déclarations. Sur cette base, le Juge cantonal n'a pas d'emblée considéré le motif de révision comme non vraisemblable ou mal fondé, dès lors qu'il a admis la demande d'effet suspensif et a demandé au ministère public de se déterminer sur la requête (cf. a contrario : arrêt 6B_574/2019 du 9 septembre 2019, la requête de révision fondée sur des déclarations écrites de l'oncle de la victime ayant été déclarée manifestement mal fondée). Le Juge a par ailleurs procédé à un examen du motif de révision invoqué au regard des éléments retenus dans la procédure au fond, et en particulier des déclarations de B._. Il n'a dès lors pas considéré que le motif était d'emblée non vraisemblable ou mal fondé.
Il n'est pas davantage fait état d'un vice de forme, d'une demande abusive, d'un défaut de motivation ou de précédents rejets de demandes de révision invoquant les mêmes motifs au sens de l'<ref-law> et de la jurisprudence y relative.
Aussi, la demande en révision ne pouvait être déclarée irrecevable. L'examen du bien-fondé du motif de révision relève de la deuxième phase du rescindant. A ce stade, la juridiction d'appel pouvait, soit rejeter la demande après avoir déterminé les compléments de preuves à administrer, le motif étant mal fondé (art. 412 al. 3 et 4; 413 al. 1 CPP; cf. par exemple, arrêts 6B_688/2020 du 15 octobre 2020 et 6B_682/2019 du 22 août 2019 en ce sens), soit constater que le motif de révision était fondé et procéder conformément à l'<ref-law>.
Cette décision relève de la compétence de la juridiction d'appel, statuant en formation collégiale au sens des art. 413 et 21 CPP. Elle ne pouvait être rendue par un juge unique (cf. s'agissant de la composition de l'autorité de recours dans le cadre d'une procédure judiciaire ultérieure indépendante: <ref-ruling> consid. 2.3 en lien avec l'<ref-law>). Cela étant, il n'y a pas lieu d'examiner la compatibilité des dispositions cantonales invoquées par l'autorité intimée avec le droit fédéral.
Au vu de ce qui précède, le recours doit être admis, l'ordonnance entreprise annulée et la cause renvoyée à la cour cantonale pour nouvelle décision, dans une composition conforme à la loi.
2.
Le recourant, qui obtient gain de cause, n'a pas à supporter de frais judiciaires (<ref-law>). Il a droit à des dépens à la charge du canton du Valais, ce qui rend sans objet sa demande d'assistance judiciaire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'ordonnance attaquée est annulée et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton du Valais versera au conseil du recourant la somme de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du Valais, Cour pénale I.
Lausanne, le 19 juillet 2021
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
La Présidente : Jacquemoud-Rossari
La Greffière : Klinke