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 (art. 183 CP). Ce jugement ne mettait pas fin aux plaintes pénales déposées pour enlèvement de mineur (art. 220 CP) 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. 