Faits:
A.
Le 11 décembre 2007, X._ a été condamné à une peine privative de liberté de quatre ans pour diverses infractions, notamment séquestration et enlèvement (<ref-law>). Ce jugement ne mettait pas fin aux plaintes pénales déposées pour enlèvement de mineur (<ref-law>) les 18 avril 2005 et 23 janvier 2007 par Y._, mère de Z._, dont X._ est le père. Ces plaintes avaient été suspendues le 5 juillet 2007.
En cours d'exécution de peine, X._ n'est pas rentré du congé dont il a bénéficié le 31 mai 2008.
Par jugement rendu par défaut le 3 mars 2009, le Tribunal pénal de la Sarine a reconnu X._ coupable d'enlèvement de mineur et l'a condamné à une peine privative de liberté de huit mois, peine complémentaire à celle infligée le 11 décembre 2007. Il a alloué à Y._ 6'000 fr. à titre de tort moral.
X._ a été extradé de Géorgie en Suisse le 13 janvier 2013. Le lendemain, il a requis le relief du jugement rendu le 3 mars 2009.
B.
Par jugement du 16 avril 2013, le Tribunal pénal de la Sarine a rejeté la demande de relief.
Par arrêt du 11 juillet 2013, la Chambre pénale du Tribunal cantonal du canton de Fribourg a rejeté le recours formé par X._ et confirmé le jugement du 16 avril 2013.
X._ a également formé un appel au plan cantonal contre le jugement par défaut du 3 mars 2009. L'appel a été suspendu jusqu'à droit connu sur la procédure de relief.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 11 juillet 2013, concluant, avec suite de dépens, à son annulation et à l'admission de sa requête de relief. Il sollicite par ailleurs l'assistance judiciaire.
Le Ministère public du canton de Fribourg conclut à l'irrecevabilité du recours, respectivement à son rejet.
Invitée à se déterminer dans un délai fixé au 15 janvier 2014, Y._ a adressé sa réponse le 17 janvier 2014 et a requis le bénéfice de l'assistance judiciaire. Elle a renoncé à se déterminer sur la tardiveté éventuelle.
X._ a adressé de brèves déterminations à la suite de celles du ministère public.

Considérant en droit:
1.
Contrairement à ce que suppose le ministère public, la procédure relative à la demande de nouveau jugement doit être traitée préalablement à l'appel (cf. <ref-law>). Le recours en matière pénale au sens des <ref-law> est ouvert contre la décision prise par une autorité supérieure en dernière instance cantonale refusant une demande de nouveau jugement à la suite d'un jugement par défaut (cf. THOMAS MAURER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 16 ad <ref-law>).
2.
Déposée hors délai (cf. <ref-law>), la réponse de l'intimée est irrecevable.
3.
Le jugement du 3 mars 2009 rendu par défaut l'a été avant l'entrée en vigueur du CPP. L'application du CPP à la demande de nouveau jugement repose sur l'<ref-law> et n'est pas contestée.
4.
Se plaignant d'arbitraire, le recourant conteste s'être abstenu d'assister volontairement à l'audience du 3 mars 2009. Invoquant une violation de l'<ref-law>, il fait valoir qu'il ignorait l'existence d'une citation à comparaître aux débats du 3 mars 2009 et qu'il n'est pas établi de manière certaine qu'il savait qu'une procédure pénale avait été reprise contre lui. Il se prévaut aussi d'une violation de l'art. 6 CEDH pour le motif qu'ignorant l'existence d'une procédure et la désignation d'un avocat d'office, il n'a pas pu bénéficier d'une défense effective.
4.1.
4.1.1. Conformément à l'<ref-law>, le tribunal rejette la demande de nouveau jugement lorsque le condamné, dûment cité, fait défaut aux débats sans excuse valable. Nonobstant les termes "sans excuse valable", c'est bien une absence fautive du condamné qui permet au tribunal de rejeter la demande de nouveau jugement (cf. THOMAS MAURER, op. cit., n° 13 ad <ref-law>). Selon le message du Conseil fédéral, le refus implique que le condamné se soit soustrait aux débats de façon manifestement fautive. Il doit être fait droit à la demande de nouveau jugement lorsqu'il n'est pas établi de manière indubitable que c'est volontairement que le prévenu ne s'est pas présenté aux débats. La réglementation devrait se rapprocher du régime des cantons les plus libéraux qui accordent au prévenu le droit à un nouveau jugement sans poser aucune condition préalable, tout en permettant d'exclure les abus flagrants (cf. Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 p. 1286).
4.1.2. Selon la jurisprudence de la Cour européenne des droits de l'homme, l'art. 6 CEDH garantit à l'accusé le droit d'être jugé en sa présence. Il s'ensuit qu'une procédure par défaut n'est compatible avec cette disposition que si le condamné a la possibilité de demander qu'une juridiction statue à nouveau, après l'avoir entendu, sur le bien-fondé de l'accusation, en fait comme en droit (arrêt de la CourEDH Sejdovic contre Italie du 1 er mars 2006, Recueil CourEDH 2006-II p. 201 § 81 s. et les arrêts cités). Ce principe supporte cependant quelques atténuations. D'abord, la Cour européenne reconnaît que, devant les juridictions supérieures, la comparution de l'accusé ne revêt pas nécessairement la même importance qu'en première instance (cf. arrêt de la CourEDH Kamasinski contre Autriche du 19 décembre 1989, série A vol. 168 § 106). Ensuite, elle admet que la CEDH n'empêche pas une personne de renoncer de son plein gré aux garanties d'un procès équitable de manière expresse ou tacite, en particulier à son droit d'être jugé en contradictoire. Elle exige seulement que la renonciation au droit de participer à l'audience se trouve établie de manière non équivoque et qu'elle ait été entourée du minimum de garanties correspondant à sa gravité (arrêt Sejdovic, § 86 et les arrêts cités). Enfin, sous réserve que les sanctions procédurales prévues ne soient pas disproportionnées et que l'accusé ne soit pas privé du droit d'être représenté par un avocat, la Cour européenne juge que le législateur national doit pouvoir décourager les absences injustifiées aux audiences (arrêt Sejdovic, § 92 et les arrêts cités, en particulier arrêt de la CourEDH Poitrimol contre France du 23 novembre 1993, série A vol. 277 A § 35). Dès lors, la Cour européenne des droits de l'homme admet qu'une personne condamnée par défaut se voie refuser la possibilité d'être jugée en contradictoire si les trois conditions cumulatives suivantes sont remplies: premièrement, il est établi que cette personne avait reçu sa citation à comparaître; deuxièmement, elle n'a pas été privée de son droit à l'assistance d'un avocat dans la procédure par défaut; et, troisièmement, il est démontré qu'elle avait renoncé de manière non équivoque à comparaître ou qu'elle avait cherché à se soustraire à la justice (cf. arrêts de la CourEDH Medenica contre Suisse du 14 juin 2001, Recueil CourEDH 2001-VI § 55 ss et Sejdovic, § 105 ss, a contrario). A propos de cette dernière condition, la Cour européenne a précisé qu'il ne devait pas incomber à l'accusé de prouver qu'il n'entendait pas se dérober à la justice ou que son absence s'expliquait par un cas de force majeure, mais qu'il était loisible aux autorités nationales d'évaluer si les excuses fournies par l'accusé pour justifier son absence étaient valables ou si les éléments versés au dossier permettaient de conclure que l'absence de l'accusé aux débats était indépendante de sa volonté (arrêt Sejdovic, § 88 et les arrêts cités; cf. aussi arrêts 6B_268/2011 du 19 juillet 2011 consid. 1.1; 6B_860/2008 du 10 juillet 2009 consid. 4.1).
4.2. La cour cantonale a exposé que le recourant avait conscience au moment du jugement du 11 décembre 2007 qu'en cas de levée de la suspension des plaintes de la mère de Z._, il s'exposait également à une condamnation pour enlèvement de mineur (<ref-law>). La mère de Z._ avait déclaré lors des débats relatifs au jugement du 11 décembre 2007 qu'elle maintenait la suspension à condition que l'enfant Z._ soit de retour en Suisse d'ici au 23 janvier 2008. Les engagements pris par le recourant à l'audience de décembre 2007 pour le retour de l'enfant en Suisse étaient mensongers et avaient pour seul but le maintien de la suspension des plaintes. Le recourant s'était volontairement dérobé à la justice en ne rentrant pas d'un congé le 31 mai 2008 accordé en cours d'exécution de la peine infligée le 11 décembre 2007. Il cherchait ainsi à éviter de prendre des mesures pour le retour de Z._ en Suisse et d'être condamné pour enlèvement de mineur. Son absence aux débats du 3 mars 2009 était par conséquent fautive et il ne se justifiait pas de donner suite à sa demande de nouveau jugement (cf. arrêt attaqué p. 5 et 6; jugement de première instance du 16 avril 2013 p. 5).
4.3. Déterminer quelle était l'intention du recourant et ce qu'il a voulu relève du contenu de la pensée, donc de l'établissement des faits, lesquels ne peuvent être revus devant le Tribunal fédéral que sous l'angle de l'arbitraire (cf. <ref-ruling> consid. 2.3.2 p. 156). En revanche, déterminer sur la base des faits retenus si l'absence du recourant aux débats était fautive ou non constitue une question de droit, que le Tribunal fédéral revoit librement.
Il ressort du jugement par défaut du 3 mars 2009 (p. 2 in fine) que la mère de l'enfant Z._ a signalé le 15 juillet 2008 souhaiter mettre fin à la suspension de ses deux plaintes pénales pour enlèvement de mineur. Elle a ainsi formulé cette requête après l'échéance pour le retour de l'enfant fixée au 23 janvier 2008 et après la fuite du recourant le 31 mai 2008. Le recourant ne formule aucun grief recevable selon l'<ref-law> pour mettre en cause sous l'angle de l'arbitraire les constatations factuelles cantonales selon lesquelles il s'est dérobé au retour de sa fille en Suisse et a cherché à éviter une condamnation pour enlèvement de mineur en s'enfuyant. Dans la mesure où il se contente d'affirmer qu'il ne savait pas qu'une procédure pénale avait été reprise contre lui, il se distancie de manière inadmissible des faits constatés, sans formuler de manière recevable au regard de l'<ref-law> un grief démontrant que ceux-ci auraient été établis de manière arbitraire. Purement appellatoires, ses critiques contre l'établissement des faits sont irrecevables (cf. <ref-ruling> consid. 4.2.3 p. 5). Il faut donc s'en tenir à la constatation selon laquelle il avait conscience de s'exposer à une condamnation pour enlèvement de mineur. Il ne fait ainsi pas de doute que dans le contexte précité, le recourant devait s'attendre à une reprise de la procédure pour les faits susceptibles de fonder une condamnation sur la base de l'<ref-law> à raison des plaintes pénales de la mère de Z._ (faits en vertu desquels il avait d'ailleurs déjà été condamné en application de l'<ref-law> par le jugement du 11 décembre 2007 [cf. jugement de première instance du 16 avril 2013 p. 5], ces deux dispositions pénales [art. 183 et 220 CP] pouvant entrer en concours idéal [cf. <ref-ruling>]).
Un courant de doctrine admet que la disparition d'un prévenu alors qu'est attendue une citation à comparaître mais qui n'est pas encore émise ne suffit pas pour rejeter une demande de nouveau jugement en considérant l'absence comme fautive (cf. SARAH SUMMERS, in Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [éd.], 2010, n° 10 ad <ref-law>, en référence à DONATSCH/SCHMID, Kommentar zur Strafprozessordnung des Kantons Zürich, n° 17 § 195 [recte § 196]). Cette approche n'exclut toutefois pas de pouvoir considérer une absence comme fautive suivant les circonstances. Tel peut être en particulier le cas lorsque le prévenu fuit dans l'optique d'échapper à une procédure pénale. En l'espèce, le recourant n'a certes pas reçu de citation personnelle pour l'audience du 3 mars 2009 et a fait l'objet d'une citation par publication officielle. Il a cependant lui-même provoqué cette situation en prenant la fuite. Selon les constatations cantonales, il s'est enfui pour éviter de respecter ses engagements quant au retour de sa fille en Suisse et pour échapper à une poursuite pénale pour enlèvement de mineur. Ces circonstances permettent d'appréhender son absence comme fautive.
4.4. Il résulte de ce qui précède que la cour cantonale n'a pas violé l'<ref-law>.
4.5. Au regard de la violation de l'art. 6 CEDH, le recourant se limite à dire qu'il n'a pas bénéficié d'une défense effective, son avocat n'ayant en particulier pas plaidé dans la procédure par défaut.
Contrairement à ce qu'affirme le recourant, il ressort du procès-verbal d'audience du 3 mars 2009 (p. 3) que Me A._ était commis comme avocat d'office pour le recourant et qu'il a plaidé, l'état de fait étant complété en ce sens (<ref-law>). Le recourant a donc bénéficié de l'assistance d'un avocat dans la procédure par défaut.
Pour le surplus, le recourant ne formule aucun grief recevable tiré d'une violation de l'art. 6 CEDH au regard des exigences de motivation posées par l'<ref-law>. Il n'y a donc pas lieu d'entrer plus avant en matière à cet égard, faute de critique recevable.
4.6. En conclusion, les circonstances d'espèce permettent de retenir que le recourant a cherché à se soustraire à la justice. Son absence peut être qualifiée de fautive, ce qui exclut de donner suite à sa demande de nouveau jugement.
5.
Le recourant succombe. Ses conclusions n'étaient cependant pas d'emblée dénuées de chance de succès et sa situation économique justifie l'octroi de l'assistance judiciaire (<ref-law>). Il n'est pas perçu de frais et Me Jacques Emery est désigné comme avocat d'office, une indemnité à titre d'honoraires lui étant allouée, supportée par la caisse du Tribunal fédéral (<ref-law>). Dès lors que l'intimée a procédé hors du délai imparti (cf. supra consid. 2), il n'y a pas lieu de lui allouer de dépens à la charge du recourant ni d'admettre sa requête d'assistance judiciaire.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire du recourant est admise.
3.
Il n'est pas perçu de frais judiciaires.
4.
Me Jacques Emery est désigné comme avocat d'office du recourant et une indemnité de 3'000 fr., supportée par la caisse du Tribunal, lui est allouée à titre d'honoraires.
5.
La demande d'assistance judiciaire de l'intimée est rejetée et il ne lui est pas alloué de dépens.
6.
Le présent arrêt est communiqué aux parties et à la Chambre pénale du Tribunal cantonal de l'Etat de Fribourg.
Lausanne, le 7 mars 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet