Faits :
A.
Par jugement du 23 janvier 2015, le Tribunal de police de Genève a reconnu A._ coupable du chef de séjour illégal (art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers, [LEtr; RS 142.20]) et l'a condamné à une peine privative de liberté d'ensemble de 60 jours, comprenant le solde de peine de 29 jours découlant de la révocation de la libération conditionnelle accordée le 25 mars 2014 (pour entrée et séjour illégal), sous déduction de la détention subie avant jugement.
B.
Par arrêt du 2 février 2016, la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision, a admis l'appel formé par A._ contre la décision de première instance et l'a acquitté du chef de séjour illégal.
L'arrêt repose en substance sur les faits suivants.
A._, ressortissant guinéen, a séjourné du 9 avril au 2 mai 2014, puis du 4 mai au 18 septembre 2014 sur le territoire suisse, en étant démuni de papiers d'identité, des autorisations et des moyens de subsistance nécessaires. Sa demande d'asile du 3 mars 2004 a fait l'objet d'une décision de non-entrée en matière du 12 mai 2004, entrée en force le 23 mai 2004. Il a été attribué au canton de Neuchâtel, dont les autorités ont indiqué n'avoir entamé aucune démarche en vue de l'exécution du renvoi, puisqu'il avait disparu des structures d'asile de leur canton le 4 juin 2004. Entendu par le Ministère public, A._ a exposé vivre en Suisse depuis 2004 et vouloir y rester, n'ayant aucun autre endroit où aller.
C.
Le Ministère public genevois forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal et conclut à sa réforme en ce sens que A._ est reconnu coupable de séjour illégal et condamné à une peine privative de liberté d'ensemble de 60 jours, sous déduction de la détention avant jugement.
Invité à se déterminer sur le recours, A._ a conclu, avec suite de frais et dépens, à son rejet et à la confirmation de l'arrêt cantonal. Il sollicite le bénéfice de l'assistance judiciaire. La cour cantonale a renoncé à se déterminer en se référant à son arrêt.

Considérant en droit :
1.
Le recourant reproche à la cour cantonale d'avoir acquitté l'intimé sur la base d'un arrêt du Tribunal fédéral qui ne présentait pas un état de fait comparable à celui déterminant en l'espèce (arrêt 6B_1172/2014 du 23 novembre 2015). Selon lui, en retenant de façon toute générale qu'en l'absence de mesures de contrainte, aucune sanction pour séjour illégal au sens de l'art. 115 al. 1 let. b LEtr ne peut être prononcée, on permet à toute personne sans titre de séjour de persister à séjourner impunément en Suisse pendant de longues périodes sans encourir de sanction. Cette interprétation contreviendrait à la volonté du législateur et à la jurisprudence fédérale constante.
1.1. L'art. 115 al. 1 let. b LEtr punit d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire quiconque séjourne illégalement en Suisse, notamment après l'expiration de la durée du séjour non soumis à autorisation ou du séjour autorisé.
En cas d'exécution immédiate du renvoi ou de l'expulsion, le juge peut renoncer à poursuivre l'étranger sorti ou entré illégalement, à le renvoyer devant le tribunal ou à lui infliger une peine (art. 115 al. 4 LEtr). Il est question de modifier cette dernière disposition afin de l'adapter à la jurisprudence européenne rendue en la matière (cf. infra consid. 1.8).
1.2. Par accord du 26 octobre 2004, entré en vigueur le 1 er mars 2008 (Accord entre la Confédération suisse, l'Union européenne et la Communauté européenne sur l'association de la Confédération suisse à la mise en oeuvre, à l'application et au développement de l'acquis de Schengen; RS 0.362.31, ci-après : AAS), la Suisse s'est engagée à mettre en oeuvre et appliquer l'acquis de Schengen.
Le 16 décembre 2008, le Parlement européen et le Conseil de l'Union européenne ont adopté la Directive relative aux normes et procédures communes applicables dans les É tats membres au retour des ressortissants de pays tiers en séjour irrégulier (Directive 2008/115/CE; ci-après: Directive sur le retour). Celle-ci vise une harmonisation minimale des procédures d'éloignement et de rapatriement pour les ressortissants de pays non-membres de Schengen (pays tiers) en séjour irrégulier, afin que les personnes concernées soient rapatriées de façon humaine et dans le respect de leurs droits fondamentaux.
Par arrêté fédéral du 18 juin 2010, la Suisse a repris le contenu de cette Directive en tant que développement de l'acquis de Schengen (Arrêté fédéral portant approbation et mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la Directive CE sur le retour; RO 2010 5925; cf. Message du 18 novembre 2009 sur l'approbation et la mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la directive CE sur le retour et sur une modification de la LEtr, in: FF 2009 p. 8043; échange de notes, in: FF 2009 p. 8085; arrêté fédéral portant approbation et mise en oeuvre de l'échange de notes entre la Suisse et la CE concernant la reprise de la directive CE sur le retour, in FF 2009 p. 8077). La mise en oeuvre de cette directive a requis une adaptation de la LEtr et de la loi fédérale du 26 juin 1998 sur l'asile (LAsi; RS 142.31); l'art. 115 al. 1 LEtr n'a, à ce jour, pas été modifié.
Comme le rappelle le Conseil fédéral dans son message, il est dans l'intérêt de toutes les parties que les règles instaurées par Schengen soient interprétées et appliquées de manière identique de part et d'autre (Message du 1 er octobre 2004 relatif à l'approbation des accords bilatéraux entre la Suisse et l'Union européenne, y compris les actes législatifs à la transposition des accords [" accords bilatéraux II "], FF 2004 5593 ss ch. 2.6.7.6). L'AAS a ainsi instauré un comité mixte qui a notamment pour mission d'observer l'application de cet accord par les différentes parties. S'il constate une différence substantielle dans l'interprétation et l'application de l'acquis de Schengen entre les autorités et juridictions suisses et la Cour de justice de l'Union européenne (ci-après: CJUE), il peut engager la procédure de règlement des différends prévue aux art. 9 al. 2 et 10 AAS qui peut aboutir, en cas d'échec, à la cessation de l'application de l'AAS.
1.3. La Directive sur le retour prévoit à son art. 6 que les États membres prennent une décision de retour à l'encontre de tout ressortissant d'un pays tiers en séjour irrégulier sur leur territoire. Selon l'art. 7 par. 1, la décision de retour fixe un délai approprié allant de sept à trente jours pour le départ volontaire, sans préjudice des exceptions visées aux par. 2 et 4. Certaines obligations visant à éviter le risque de fuite, comme les obligations de se présenter régulièrement aux autorités, de déposer une garantie financière adéquate, de remettre des documents ou de demeurer en un lieu déterminé, peuvent être imposées pendant le délai de départ volontaire (art. 7 par. 3). S'il existe un risque de fuite, ou si une demande de séjour régulier a été rejetée comme étant manifestement non fondée ou frauduleuse, ou si la personne concernée constitue un danger pour l'ordre public, la sécurité publique ou la sécurité nationale, les États membres peuvent s'abstenir d'accorder un délai de départ volontaire ou peuvent accorder un délai inférieur à sept jours (art. 7 par. 4).
Sous le titre marginal " éloignement ", l'art. 8 de la Directive sur le retour prévoit que les É tats membres prennent toutes les mesures nécessaires pour exécuter la décision de retour si aucun délai n'a été accordé pour un départ volontaire (cf. art. 7 par. 4), ou si l'obligation de retour n'a pas été respectée dans le délai accordé pour le départ volontaire conformément à l'art. 7. Les art. 15 ss de la Directive sur le retour règlent les conditions de rétention à des fins d'éloignement. En principe, à moins que d'autres mesures suffisantes, mais moins coercitives, puissent être appliquées efficacement dans un cas particulier, les É tats membres peuvent uniquement placer en rétention le ressortissant d'un pays tiers qui fait l'objet de procédures de retour afin de préparer le retour et/ou de procéder à l'éloignement (art. 15).
1.4. La CJUE a examiné la compatibilité de législations nationales prévoyant diverses sanctions (notamment l'amende ou l'emprisonnement) en cas de séjour illégal avec la Directive sur le retour. La jurisprudence européenne ayant évolué au fil des années et des questions posées par les autorités judiciaires nationales, il y a lieu de mettre en évidence les principes dégagés en matière de punissabilité du séjour illégal.
1.4.1. A teneur de l'arrêt El Dridi, la Directive sur le retour (notamment ses art. 15 et 16) s'oppose à une réglementation qui prévoit une peine d'emprisonnement à un ressortissant d'un pays tiers en séjour irrégulier pour le seul motif que celui-ci demeure, en violation d'un ordre de quitter le territoire de cet État dans un délai déterminé, sur ledit territoire sans motif justifié. Les États doivent poursuivre leurs efforts en vue de l'exécution de la décision de retour qui continue de produire ses effets. Ce n'est que dans l'hypothèse où l'exécution de la décision de retour sous forme d'éloignement risque d'être compromise par le comportement de l'intéressé que les États peuvent procéder à la privation de liberté de ce dernier au moyen d'une rétention. Celle-ci doit être aussi brève que possible et maintenue qu'aussi longtemps que le dispositif d'éloignement est en cours et exécuté avec toute la diligence requise (arrêt CJUE C-61/11 du 28 avril 2011 par. 39 s., 58 et 62). La Directive sur le retour établit l'ordre de déroulement des étapes de la procédure de retour correspondant à une gradation des mesures à prendre en vue de l'exécution de la décision de retour, gradation allant de la mesure qui laisse le plus de liberté à l'intéressé (octroi d'un délai pour un départ volontaire) à des mesures qui restreignent le plus celle-ci (rétention dans un centre spécialisé) (arrêt CJUE C-61/11 PPU du 28 avril 2001 CJUE par. 41). Dans cet arrêt, la CJUE n'a pas expressément répondu à la première question préjudicielle de l'État membre relative à la possibilité générale de sanctionner pénalement la violation d'une étape intermédiaire de la procédure administrative de retour (non-respect du seul ordre d'éloignement) avant que celle-ci ne soit achevée (arrêt CJUE C-61/11 du 28 avril 2011 par. 25).
1.4.2. Dans l'arrêt Achughbabian, la CJUE rappelle que la Directive sur le retour ne s'oppose pas à ce que le droit d'un État membre qualifie le séjour irrégulier de délit et prévoie des sanctions pénales pour dissuader et réprimer la commission d'une telle infraction aux règles nationales en matière de séjour (arrêt CJUE C-329/11 du 6 décembre 2011 par. 28). En revanche, elle retient que cette Directive s'oppose à une réglementation permettant l'emprisonnement d'un ressortissant d'un pays tiers qui, tout en séjournant irrégulièrement sur le territoire dudit État et n'étant pas disposé à quitter ce territoire volontairement, n'a pas été soumis aux mesures coercitives visées à l'art. 8 et n'a pas, en cas de placement en rétention en vue de la préparation et de la réalisation de son éloignement, vu expirer la durée maximale de cette rétention. Enfin, selon la CJUE, la Directive sur le retour ne s'oppose pas à l'emprisonnement d'un ressortissant d'un pays tiers auquel la procédure de retour établie par la Directive a été appliquée et qui séjourne irrégulièrement sur ledit territoire sans motif justifié de non-retour (arrêt CJUE C-329/11 du 6 décembre 2011 par. 50). A teneur de cet arrêt, le prononcé d'une décision de retour (fixant ou non un délai pour le départ volontaire) fait naître l'obligation imposée par l'art. 8 de la Directive sur le retour à l'État concerné, de prendre toutes les mesures nécessaires pour procéder à l'éloignement (cf. art. 3 par. 5), à savoir le transfert physique de l'intéressé hors de l'État (arrêt CJUE C-329/11 du 6 décembre 2011 par. 35). Or, l'infliction et l'exécution d'une peine d'emprisonnement au cours de la procédure de retour ne contribuent pas à la réalisation de l'éloignement que cette procédure poursuit. Une telle peine ne constitue donc pas une " mesure " ou une " mesure coercitive " au sens de l'art. 8 de la Directive (arrêt CJUE C-329/11 du 6 décembre 2011 par. 37).
1.4.3. Dans l'affaire Sagor, la CJUE rappelle que la Directive sur le retour ne s'oppose pas à ce que le droit d'un État membre qualifie le séjour irrégulier de délit et prévoie des sanctions pénales pour dissuader et réprimer la commission d'une telle infraction (arrêt CJUE C-430/11 du 6 décembre 2012 par. 31; cf. également arrêt Achughbabian précité par. 28). La CJUE considère que le prononcé d'une peine pécuniaire (pouvant être remplacée par une peine d'expulsion) n'empêche en aucune manière qu'une décision de retour soit prise et mise en oeuvre dans le plein respect des conditions énoncées aux art. 6 à 8 de la Directive et ne porte pas non plus atteinte aux normes communes en matière de privation de liberté énoncées aux art. 15 et 16 (arrêt CJUE C-430/11 du 6 décembre 2012 par. 36, 47, 50). En l'occurrence, le retour peut être réalisé indépendamment de la poursuite pénale et sans que celle-ci doive avoir abouti (arrêt CJUE C-430/11 du 6 décembre 2012 par. 35). En revanche, l'infliction et l'exécution d'une assignation à résidence au cours de la procédure de retour ne contribue pas à la réalisation de l'éloignement. Une telle peine ne constitue donc pas une mesure ou une mesure coercitive au sens de l'art. 8 de la Directive. Un risque d'atteinte à la procédure de retour existe notamment si la réglementation applicable ne prévoit pas que l'exécution d'une peine d'assignation à résidence doit prendre fin dès qu'il est possible de réaliser l'éloignement (arrêt CJUE C-430/11 du 6 décembre 2012 par. 43 ss, 47, 50).
1.4.4. L'arrêt Zaizoune met en évidence l'obligation imposée par l'art. 8 de la Directive sur le retour de procéder à l'éloignement du ressortissant étranger en séjour irrégulier, dans les meilleurs délais (arrêt CJUE C-38/14 du 23 avril 2015 par. 34). Ainsi, une réglementation qui prévoit, en cas de séjour irrégulier d'imposer, selon les circonstances, soit une amende, soit l'éloignement en tant que mesures exclusives l'une de l'autre (l'amende étant incompatible avec l'éloignement du territoire national) est contraire aux principes issus de la Directive sur le retour (arrêt CJUE C-38/14 du 23 avril 2015 par. 41 s.).
1.4.5. Dans l'arrêt Celaj, la CJUE considère que la Directive sur le retour ne s'oppose pas, en principe, à une réglementation qui prévoit une peine d'emprisonnement à un ressortissant d'un pays tiers en situation de séjour irrégulier qui, après être retourné dans son pays d'origine dans le cadre d'une procédure de retour antérieure, entre de nouveau irrégulièrement sur le territoire dudit État en violation d'une interdiction d'entrée (arrêt CJUE C-290/2014 du 1 er octobre 2015 par. 33).
1.4.6. L'arrêt Affum traite de la pénalisation d'une personne en transit et conclut que la Directive sur le retour doit être interprétée en ce sens qu'elle s'oppose à une réglementation permettant, du seul fait de l'entrée irrégulière par une frontière intérieure conduisant au séjour irrégulier, l'emprisonnement d'un ressortissant d'un pays tiers, pour lequel la procédure de retour établie par cette directive n'a pas encore été menée à son terme (arrêt CJUE C-47/15 du 7 juin 2016 par. 93 s.).
1.5. En définitive, il ressort en substance de la jurisprudence européenne que la Directive sur le retour ne s'oppose pas à la pénalisation du séjour illégal. Celle-ci ne doit toutefois pas mettre en péril le renvoi effectif de l'intéressé. Or, le prononcé ou l'exécution d'une peine privative de liberté peuvent empêcher ou entraver le bon déroulement de la procédure de renvoi. Une telle sanction n'est compatible avec la Directive sur le retour qu'à condition que l'intéressé a été soumis aux mesures coercitives visées à l'art. 8 de la Directive sur le retour (cf. infra consid. 3.1). La peine pécuniaire n'est quant à elle pas susceptible d'entraver la procédure de retour établie par la Directive, pour autant que l'État concerné respecte son obligation de prendre une décision de retour à l'encontre du ressortissant d'un pays tiers en séjour irrégulier et que la sanction n'exclut pas l'éloignement de l'intéressé.
1.6. Sur le plan interne, le Tribunal fédéral a fixé des principes en matière de punissabilité du séjour illégal selon l'art. 115 al. 1 let. b LEtr.
1.6.1. De jurisprudence constante, la punissabilité du séjour irrégulier suppose que l'étranger ne se trouve pas dans l'impossibilité objective - par exemple en raison d'un refus du pays d'origine d'admettre le retour de ses ressortissants ou de délivrer des papiers d'identité - de quitter la Suisse et de rentrer légalement dans son pays d'origine. En effet, le principe de la faute suppose la liberté de pouvoir agir autrement (arrêt 6B_320/2013 du 29 août 2013 consid. 2.1 et les arrêts cités; cf. également arrêts 6B_139/2014 du 5 août 2014 consid. 2; 6B_482/2010 du 7 octobre 2010 consid. 3.2.2 et 3.2.3).
Dans un arrêt du 7 octobre 2010, rendu avant les arrêts topiques de la CJUE, le Tribunal fédéral a considéré que le ressortissant étranger faisant l'objet d'une décision de renvoi avec ordre de quitter la Suisse immédiatement, qui disparaissait après l'entrée en force de la décision et ne collaborait d'aucune manière à l'établissement de documents de voyage, se rendait coupable d'infraction à l'art. 115 al. 1 let. b LEtr. Il ne pouvait faire valoir l'impossibilité objective de quitter la Suisse. Sa condamnation à une peine pécuniaire de 70 jours-amende avec sursis ne prêtait pas flanc à la critique (arrêt 6B_482/2010 du 7 octobre 2010).
1.6.2. Depuis les arrêts principaux El Dridiet Achughbabian, le Tribunal fédéral a rendu plusieurs arrêts sur la compatibilité de l'application de l'art. 115 al. 1 let. b LEtr avec la Directive sur le retour. Compte tenu de l'évolution de la jurisprudence européenne et des adaptations que celle-ci implique sur le plan national, il y a lieu d'exposer succinctement les arrêts rendus par le Tribunal fédéral depuis 2011 (arrêts El Dridiet Achughbabian), respectivement, fin 2012 (arrêt Sagor).
En substance, selon le Tribunal fédéral, la Directive sur le retour n'exclut pas l'application des dispositions pénales nationales lorsque les autorités administratives ont entrepris toutes les mesures raisonnables pour l'exécution de la décision de retour mais que la procédure de retour a échoué en raison du comportement de l'intéressé (arrêts 6B_139/2014 du 5 août 2014 consid. 2; 6B_173/2013 du 19 août 2013 consid. 1.4; 6B_188/2012 du 17 avril 2012 consid. 5 et les arrêts cités). Sous cet angle, ces arrêts ne s'opposent pas à la jurisprudence européenne.
Dans quatre affaires, les recours formés contre des condamnations du chef de séjour illégal à des peines privatives de liberté allant de 2 à 6 mois ont été rejetés dans la mesure où aucune démarche administrative supplémentaire en vue du renvoi des recourants n'était exigible, faute de collaboration de ces derniers (arrêts 6B_188/2012 du 17 avril 2012 consid. 5 et 6B_525/2014 du 9 octobre 2014 consid. 1.2) ou faute de se trouver dans une hypothèse visée par les arrêts européens (arrêts 6B_196/2012 du 24 janvier 2013 consid. 2.1.3 et 2.2 et 6B_320/2013 du 29 août 2013 consid. 3, ce dernier arrêt étant critiqué en doctrine sous l'angle de l'art. 2 par. 2 let. b de la Directive sur le retour, cf. CATHERINE HAGUENAU-MOIZARD, La pénalisation du séjour irrégulier en droit européen, en droit français et en droit suisse, in Schengen et Dublin en pratique [Stephan Breitenmoser et al. (éd.)], 2015, p. 183 et ALEXANDRA BÜCHLER, die Konsequenzen des rechtswidrigen Aufenhalts von Drittstaatsangehörigen in der Schweiz, in Annuaire du droit de la migration 2015/2016, p. 107). Dans deux arrêts du 11 mars 2013 (arrêts 6B_617/2012 et 6B_618/2012 consid. 1.5), le Tribunal fédéral a admis les recours formés par le ministère public contre les classements prononcés en faveur de prévenus du chef de séjour illégal (peines privatives de liberté de 3 mois prononcées en première instance), considérant que toutes les mesures administratives raisonnables en vue du renvoi avaient été entreprises (notamment demandes d'établissement de papiers de voyage) et retenant que les prévenus refusaient de rentrer volontairement dans leur pays. Par ailleurs, tenant compte des circonstances des cas d'espèce, le Tribunal fédéral a considéré que les peines privatives de liberté de 3 mois prononcées en première instance, n'étaient pas de nature à empêcher ou entraver l'expulsion des prévenus (arrêts 6B_617/2012 et 6B_618/2012 du 11 mars 2013 consid. 1.5, ces arrêts ont été commentés en doctrine, cf. MINH SON NGUYEN, Jurisprudence et analyses du 1 er janvier au 30 juin 2013, in Dang/Petry [éd.] Actualité du droit des étrangers, 2013, vol. 1, p. 57, selon lequel le manque de collaboration des prévenus n'est pas pertinent dès lors qu'il appartient, dans ce cas, à l'État d'entreprendre des mesures coercitives au sens de l'art. 8 de la Directive sur le retour; CATHERINE HAGUENAU-MOIZARD, op. cit., p. 182 et ALEXANDRA BÜCHLER, op. cit., p. 106, considèrent quant à elles que ces arrêts respectent la Directive sur le retour, respectivement la jurisprudence européenne).
Dans un arrêt du 19 avril 2013 (arrêt 6B_713/2012 consid. 1.5), le Tribunal fédéral a considéré qu'à la lumière de la jurisprudence européenne, la seule affirmation du ressortissant étranger selon laquelle il ne souhaitait pas quitter la Suisse n'était pas suffisante pour fonder sa culpabilité de séjour illégal, en l'absence de mise en place de mesures administratives. Il ressortait toutefois des pièces du dossier que le prévenu avait été renvoyé de force en 2001, qu'il faisait l'objet d'une décision de renvoi prononcée en 2009, que la police cantonale compétente était chargée de son expulsion et qu'il avait par la suite disparu. Le Tribunal fédéral a ainsi retenu que toutes les démarches administratives raisonnables pour l'exécution du renvoi avaient été entreprises et a rejeté le recours formé contre la condamnation du recourant à une peine pécuniaire de 60 jours-amende pour séjour illégal (arrêt 6B_713/2012 du 19 avril 2013 consid. 1.5). Par arrêt du 5 août 2014, le Tribunal fédéral a considéré que le prononcé d'une peine pécuniaire de 40 jours-amende avec sursis n'empêchait pas ni n'entravait la procédure de retour de sorte que cette condamnation du chef de séjour illégal ne prêtait pas flanc à la critique (arrêt 6B_139/2014 du 5 août 2014 consid. 3). Il ressortait de l'état de fait de cette affaire que les autorités administratives n'avaient entrepris aucune mesure de contrainte dès lors que le recourant semblait organiser personnellement son retour (arrêt 6B_139/2014 du 5 août 2014 consid. 3).
Dans des arrêts plus récents, le Tribunal fédéral a admis les recours formés contre la condamnation du chef de séjour illégal, faute pour les autorités administratives compétentes d'avoir entrepris les mesures de contrainte nécessaires en vue du renvoi (arrêts 6B_1172/2014 du 23 novembre 2015 et 6B_106/2016 du 7 décembre 2016). Dans l'arrêt 6B_1172/2014, le Tribunal fédéral a en outre considéré que la peine pécuniaire (60 jours-amende) était propre à entraver et à retarder le retour de la recourante et contrevenait à la Directive sur le retour. La recourante a dès lors été acquittée (arrêt critiqué par ALEXANDRA BÜCHLER, op. cit., p. 108, selon laquelle, cet arrêt semble, d'une part, reconnaître une priorité générale de la procédure de renvoi sur la procédure pénale, indépendamment du type de peine prononcée et, d'autre part, omettre que l'arrêt Sagor retient précisément qu'une peine pécuniaire n'entrave pas la procédure de renvoi). Dans son arrêt 6B_106/2016 du 7 décembre 2016, le Tribunal fédéral a jugé que la peine privative de liberté de 45 jours infligée au recourant contrevenait à la Directive sur le retour, la procédure de renvoi n'ayant pas été menée jusqu'à son terme sans succès. L'arrêt cantonal a été annulé et renvoyé à la cour cantonale pour nouvelle décision.
1.7. En doctrine, certains auteurs déduisent des arrêts El Dridiet Achughbabian que la procédure pénale doit être précédée par la procédure administrative de retour avec toutes ses étapes. La condamnation pénale n'est admise qu'en cas d'impossibilité de mise en oeuvre de mesures coercitives en vue du renvoi (THOMAS HUGI YAR, Das Urteil El Dridi, die EU-Rückführungsrichtlinie und der Schengen-Besitzstand, in jusletter du 11 juillet 2011, n° 11, 16; ANDREAS ZÜND, in Spescha et al. [éd.], Kommentar Migrationsrecht, 4e éd. 2015, n° 9 ad art. 80, n° 12 ad art. 115 LEtr; SARAH PROGIN-THEUERKAUF, Zur Auslegung der Begriffe " Massnahmen " und " Zwangsmassnahmen " in Art. 8 Abs. 1 und 4 der Eu-Rückführungsrichtlinie, in Revue Suisse pour la pratique et le droit d'asile, Asyl 2/12, p. 37). Le principe de l'opportunité posé à l'art. 115 al. 4 LEtr constituerait ainsi un véritable obstacle à la poursuite pénale (ANDREAS ZÜND, ibidem). Ces avis de doctrine, hormis celui de ZÜND, précèdent la jurisprudence européenne rendue fin 2012.
Prenant en compte la jurisprudence européenne postérieure, en particulier l'arrêt Sagor, d'autres auteurs estiment que la procédure pénale, voire la sanction pénale (sous forme de peine pécuniaire), sont possibles tant qu'elles ne privent pas la Directive sur le retour de son effet utile, ce même pendant la procédure administrative de renvoi (ALEXANDRA BÜCHLER, op. cit., p. 94 s., 102 s. et 104; CATHERINE HAGUENAU-MOIZARD, op. cit., p. 175 et 182; MINH SON NGUYEN, op. cit., p. 54 et 56). En référence à l'arrêt Sagor, ZÜND indique qu'une simple peine pécuniaire n'entrave pas la procédure de retour, de sorte que celle-ci est admissible (ANDREAS ZÜND, op. cit., n° 12 ad art. 115 LEtr).
1.8.
1.8.1. En juin 2016, le Conseil fédéral a lancé la procédure de consultation relative à la révision de la LEtr, notamment afin d'adapter cette dernière à la Directive sur le retour, à la suite de l'évaluation Schengen de la Suisse en 2014. Le projet de loi propose une modification de l'art. 115 al. 4 LEtr en ce sens que, lorsqu'une procédure de renvoi est prévue ou pendante, l'autorité compétente pourra renoncer à poursuivre pénalement, à renvoyer devant le tribunal ou à infliger une peine à un étranger illégalement entré en Suisse ou sorti de Suisse ou qui y séjourne illégalement. D'après le rapport explicatif, la modification proposée permet la primauté de l'exécution d'un renvoi sur une peine privative de liberté, dans le sens de la jurisprudence fédérale et européenne, non seulement si le renvoi est possible dans l'immédiat, mais aussi tant qu'une procédure de renvoi est pendante ou lorsqu'une telle procédure doit être ouverte en application de la Directive sur le retour (cf. Rapport explicatif, Adaptations de la loi sur les étrangers (LEtr) " Normes procédurales et systèmes d'information ", Commentaire de l'art. 115 al. 4 P-LEtr, p. 37; cf. THOMAS HUGI YAR, op. cit., n° 16; ALEXANDRA BÜCHLER, op. cit., p. 109 s., qui estiment nécessaire de clarifier la subsidiarité de la procédure pénale à la procédure d'éloignement par le biais de l'art. 115 al. 4 LEtr).
1.8.2. Compte tenu de la jurisprudence européenne et fédérale et conformément à l'opinion de la doctrine la plus récente, force est de constater que, en l'état, l'art. 115 al. 4 LEtr - lequel ne vise pas expressément le séjour illégal - ne saurait être interprété comme obstacle général à la poursuite pénale en cas de mise en oeuvre d'une procédure administrative de renvoi. Ce d'autant que le législateur s'est saisi de la question sous forme potestative (Kann-Vorschrift) dans le projet de modification de la LEtr.
1.9. Au vu de ce qui précède, il sied de retenir que la Directive sur le retour ne s'oppose pas à ce que le droit pénal suisse réprime le séjour illégal lorsqu'une procédure de retour est mise en oeuvre. En ce sens, elle ne s'oppose pas à ce que le séjour illégal soit érigé en infraction. Sur le plan de la sanction, une application de l'art. 115 al. 1 let. b LEtr conforme à la Directive sur le retour et à la jurisprudence européenne impose qu'il soit renoncé à prononcer et à exécuter une peine privative de liberté lorsque l'intéressé en séjour illégal fait l'objet d'une décision de renvoi et que les mesures nécessaires pour procéder à l'éloignement n'ont pas encore été mises en oeuvre. C'est la solution adoptée par l'arrêt du Tribunal fédéral le plus récent qu'il convient de suivre (arrêt 6B_106/2016 du 7 décembre 2016). En revanche, le prononcé d'une peine pécuniaire n'est pas incompatible avec la Directive sur le retour, pour autant qu'elle n'entrave pas la procédure de retour. Une telle sanction ne nécessite pas, à teneur de la jurisprudence européenne rendue à ce jour, que toutes les mesures nécessaires au renvoi aient préalablement été mises en oeuvre. En cela, il y a lieu de s'écarter de la solution retenue dans l'arrêt 6B_1172/2014 du 23 novembre 2015, critiqué par la doctrine (cf. ALEXANDRA BÜCHLER, op. cit., p. 108).
2.
En l'espèce, la cour cantonale a acquitté l'intimé en considérant que la procédure administrative de renvoi n'avait pas été menée à son terme, le cas échéant par le biais de mesures de contrainte prévues par la LEtr.
Or, s'il est vrai que l'absence de mesure administrative nécessaire à l'exécution du retour empêche le prononcé d'une peine privative de liberté, rien ne s'oppose à ce que l'intimé soit reconnu coupable de séjour illégal, pour autant que les conditions de l'infraction soient réalisées.
D'une part, il est établi et non contesté que l'intimé a séjourné illégalement en Suisse, d'autre part, il n'apparaît pas qu'il fût dans une situation d'impossibilité objective de retour (cf. arrêt entrepris, consid. 2.1.3 et 2.2 p. 7, notamment sur les accords conclus entre la Guinée et la Suisse). L'intimé ne le prétend d'ailleurs pas. Aussi, au vu des développements qui précèdent (cf. supra consid. 1), il y a lieu de reconnaître l'intimé coupable de séjour illégal au sens de l'art. 115 al. 1 let. b LEtr. En acquittant l'intimé de ce chef d'infraction, la cour cantonale a violé le droit fédéral.
3.
Cela étant, dans la mesure où le recourant conclut tant à la condamnation de l'intimé pour séjour illégal, qu'au prononcé d'une peine privative de liberté d'ensemble de 60 jours, il convient d'examiner si la procédure administrative de renvoi a été mise en oeuvre au moyen des mesures nécessaires.
3.1. Si la Directive sur le renvoi fixe comme objectif l'exécution de la décision de retour de manière efficace et proportionnée en recourant à toutes les " mesures nécessaires " pour ce faire, elle ne contient pas de liste de mesures, respectivement, de mesures coercitives pour exécuter la décision de retour au sens de l'art. 8. Selon la jurisprudence européenne, les termes " mesures " et " mesures coercitives " se réfèrent à toute intervention qui conduit de manière efficace et proportionnée au retour de l'intéressé (cf. arrêt CJUE Achughbabian C-329/11 du 6 décembre 2011 par. 36). Les modalités concrètes sont laissées à l'appréciation des États dans leur législation et leur pratique administrative (Manuel sur le retour, annexe à la recommandation de la Commission Européenne du 1 er octobre 2015 établissant un " Manuel sur le retour " commun devant être utilisé par les autorités compétentes des États membres lorsqu'elles exécutent des tâches liées au retour, p. 45).
En droit suisse, l'art. 64d LEtr prévoit que la décision de renvoi est assortie en principe d'un délai de départ raisonnable (al. 1) et dresse une liste des exceptions (al. 2). L'art. 64e LEtr permet à l'autorité compétente d'obliger l'étranger concerné à se présenter régulièrement à une autorité (let. a); fournir des sûretés financières appropriées (let. b); déposer des documents de voyage (let. c). L'art. 69 LEtr régit la procédure d'exécution du renvoi ou de l'expulsion et l'art. 70 LEtr prévoit les conditions de la perquisition, respectivement de la fouille. Constituent des mesures de contrainte au sens de la LEtr, la rétention (art. 73 LEtr), l'assignation d'un lieu de résidence et l'interdiction de pénétrer dans une région déterminée (art. 74 LEtr) et les différentes formes de détention administrative (art. 75 ss LEtr). Les cantons sont libres de prévoir d'autres mesures qui poursuivent le même but (ALEXANDRA BÜCHLER, op. cit., p. 87; MARIE KHAMMAS, Wegweisungsvollzug und Zwangsmassnahmen, in Schweizerische Flüchtlingshilfe [éd.], Handbuch zum Asyl- und Wegweisungsverfahren, 2 ème éd. 2015, p. 411, 418).
La question se pose de savoir si la notion de " mesures nécessaires à l'exécution de retour " au sens de l'art. 8 de la Directive sur le retour correspondent à celles prévues par la LEtr. Il ressort de la jurisprudence rendue en lien avec l'art. 115 LEtr que la demande par l'autorité compétente de documents de voyage (arrêts 6B_617/2012 et 6B_618/2012 du 11 mars 2013) ou le mandat donné aux autorités compétentes d'exécuter le renvoi (arrêts 6B_713/2012 du 19 avril 2013 et 6B_139/2014 du 5 août 2014) constituent de telles mesures. Les arrêts les plus récents mentionnent exclusivement les mesures de contrainte prévues par la LEtr en se référant notamment aux art. 73 à 78 (arrêts 6B_1172/2014 du 23 novembre 2015 consid. 1.3 et 6B_106/2016 du 7 décembre 2016 consid. 1.5). Cette question peut souffrir de demeurer indécise en l'espèce compte tenu de ce qui suit.
3.2. A teneur de l'état de fait cantonal, les autorités compétentes neuchâteloises ont indiqué n'avoir entamé aucune démarche en vue de l'exécution de la décision du renvoi de l'intimé, exécutoire depuis le 23 mai 2004 puisque celui-ci avait disparu des structures d'asile de leur canton le 4 juin 2004.
Le recourant affirme que les autorités administratives auraient entrepris les démarches nécessaires au renvoi, en particulier des mesures de contrainte au sens de l'art. 74 LEtr, sous la forme de mesures d'assignation et d'interdiction. Or, s'il ressort de l'arrêt entrepris que l'intimé a été condamné à deux reprises, entre le 18 janvier 2005 et le 5 novembre 2010, pour non-respect d'une assignation à un lieu de résidence ou interdiction de pénétrer dans une région déterminée, ces éléments ne rendent pas insoutenable la constatation selon laquelle aucune mesure administrative en vue de l'éloignement de l'intimé n'a été entreprise (cf. art. 105 al. 1 et 106 al. 2 LTF). Ainsi, dans la mesure où le recourant échoue à remettre en cause l'absence de toute intervention conduisant de manière efficace au retour de l'intéressé (cf. supra consid. 3.1), les différentes allégations selon lesquelles ce dernier se serait soustrait à la procédure de renvoi ou l'aurait rendue impossible, sont vaines.
Dans ces circonstances, force est de constater qu'une condamnation à une peine privative de liberté contreviendrait à la Directive sur le retour (cf. consid. 16 de la Directive sur le retour: la rétention n'est justifiée que pour préparer le retour ou procéder à l'éloignement et si l'application de mesures moins coercitives ne suffisent pas; Manuel sur le retour, op. cit., p. 46: la seule privation de liberté autorisée dans le contexte du retour est la rétention à des fins d'éloignement au titre de l'art. 15 de la Directive sur le retour).
4.
Au vu de ce qui précède, le recours doit être partiellement admis, l'arrêt entrepris annulé et la cause renvoyée à la cour cantonale pour qu'elle reconnaisse l'intimé coupable de séjour illégal au sens de l'art. 115 al. 1 let. b LEtr. Elle devra examiner s'il y a lieu de prononcer une peine autre qu'une peine privative de liberté, cas échéant, dans le respect de la jurisprudence relative au délit continu au regard des autres condamnations déjà prononcées (cf. <ref-ruling> consid. 3.2 p. 9; arrêt 6B_1226/2013 du 31 mars 2014 consid. 1.1).
Le ministère public, qui obtient partiellement gain de cause, ne saurait se voir allouer de dépens (<ref-law>). La requête d'assistance judiciaire de l'intimé doit être admise au vu de sa situation financière et une indemnité appropriée doit être accordée à son conseil d'office, à charge de la caisse du Tribunal fédéral (<ref-law>). L'intimé est toutefois rendu attentif au fait qu'il devra rembourser cette dernière, s'il peut ultérieurement le faire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis, l'arrêt attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision.
2.
La demande d'assistance judiciaire de l'intimé est admise pour la procédure devant le Tribunal fédéral.
3.
Il n'est pas perçu de frais judiciaires.
4.
Me Jacques Emery est désigné comme avocat d'office de l'intimé et une indemnité de 1'000 fr., supportée par la caisse du Tribunal fédéral, lui est allouée à titre d'honoraires.
5.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 15 mai 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke