Faits : A. A.a. B._, née en 1989, et A._, né en 1976, tous deux de nationalité algérienne, se sont mariés à U._ (Algérie) le 2 juin 2013. Le 4 octobre 2013, B._ est venue rejoindre son époux en Suisse où celui-ci est domicilié depuis 2006. A.b. En mai 2014, alors qu'elle était enceinte, B._ a quitté le domicile conjugal, alléguant que son époux la séquestrait dans leur appartement et lui imposait des règles strictes, telles que l'interdiction de sortir seule ou le port du voile. Elle a déposé par la suite une plainte pénale pour séquestration et contrainte, accusations que A._ a contestées, déposant à son tour une plainte pénale contre son épouse pour calomnie, diffamation, dénonciation calomnieuse et induction de la justice en erreur. Le dossier ne contient pas d'autre élément quant à la suite de ces procédures. Dans un premier temps, B._ a été hébergée chez sa famille et une connaissance, puis a logé dans un foyer d'urgence dès le 25 juillet 2014. La fille commune des parties, C._, est née le 18 août 2014 à Genève. B. B.a. Le 12 août 2014, A._ a déposé une requête de divorce en Algérie tendant à la dissolution du lien conjugal. B.b. Par acte du 4 septembre 2014, B._ a saisi le Tribunal de première instance du canton de Genève (ci-après: le Tribunal) d'une requête de mesures protectrices de l'union conjugale, sollicitant, notamment, l'autorisation de vivre séparée de son époux, l'attribution en sa faveur de la garde de l'enfant C._, en réservant un droit de visite à A._ selon les prescriptions du Service de protection des mineurs (ci-après: le SPMi) et la condamnation de A._ à lui verser, par mois et d'avance, un montant de 2'000 fr. à titre de contribution à l'entretien de la famille, soit 1'000 fr. pour l'entretien de sa fille et 1'000 fr. pour son propre entretien, dès le 1 er juin 2014. B.c. Lors de l'audience du 18 novembre 2014 devant le Tribunal, A._ a soulevé une exception de litispendance, compte tenu de la procédure de divorce pendante en Algérie. Il a conclu à l'irrecevabilité de la requête de son épouse, alléguant que le Tribunal aurait dû être saisi d'une demande de mesures provisionnelles et non pas d'une requête de mesures protectrices. B._ s'est opposée à l'incident, contestant la compétence des tribunaux algériens en raison du domicile des parties en Suisse. B.d. Par jugement sur incident du 23 janvier 2015, le Tribunal a admis sa compétence pour connaître de la requête de mesures protectrices formée par B._, au motif que les tribunaux suisses pouvaient ordonner des mesures provisoires, respectivement des mesures protectrices de l'union conjugale, en vertu de l'art. 10 let. b LDIP, quand bien même une action en divorce était pendante uniquement devant un juge étranger, pour autant que les mesures requises soient urgentes et nécessaires, ce qui paraissait être le cas en l'occurrence. C. C.a. Le 28 janvier 2015, le Tribunal de U._ (Algérie) a prononcé le divorce des époux, se déclarant au préalable compétent en application de l'art. 12 du Code civil algérien, compte tenu de la nationalité algérienne des deux parties et du fait qu'elles avaient contracté mariage en Algérie. Il a, en outre, condamné A._ à verser à B._ la somme de 30'000 dinars (équivalent à 280 fr.) à titre de pension de retraite légale. En revanche, il ne s'est pas prononcé sur le sort du domicile conjugal ni sur le sort de l'enfant, n'ayant pas été saisi de ces questions. C.b. Le 29 juin 2015, A._ a fait transcrire le jugement de divorce algérien du 28 janvier 2015 au Registre suisse de l'Etat civil. C.c. Par courrier adressé le 21 octobre 2015 à la Direction cantonale de l'Etat civil, B._ a contesté la transcription du jugement de divorce algérien et requis la rectification du registre, déclarant avoir eu connaissance de dite transcription le jour même. D. D.a. Par jugement de mesures protectrices de l'union conjugale du 30 juin 2015, notifié aux parties avec sa motivation complète le 5 octobre 2015, le Tribunal a notamment autorisé les époux A._ et B._ à vivre séparés (ch. 1 du dispositif), attribué à B._ la garde sur l'enfant C._ (ch. 2), réservé à A._ un droit de visite s'exerçant, dans un premier temps au sein d'un Point Rencontre, à raison de deux heures par quinzaine (ch. 3), instauré une curatelle de surveillance et d'organisation du droit de visite au sens de l'art. 308 al. 2 CC (ch. 4), condamné A._ à verser en mains de B._, par mois et d'avance, allocations familiales éventuelles non comprises, le montant de 500 fr. à compter du 1 er juin 2014 au titre de contribution à l'entretien de sa famille (ch. 6) et attribué la jouissance du domicile conjugal, de même que les droits et obligations y relatifs, à B._ (ch. 7). Le Tribunal a prononcé ces mesures pour une durée indéterminée (ch. 10). D.b. Le 15 octobre 2015, A._ a appelé de ce jugement par-devant la Cour de justice du canton de Genève (ci-après: Cour de justice) requérant l'annulation des seuls ch. 6 et 7 de son dispositif et leur réforme en ce sens qu'il est condamné à verser en mains de B._, allocations familiales non comprises, une contribution d'entretien mensuelle pour l'enfant de 150 fr. pour les mois de mars à juin 2015, qu'il est libéré de toute contribution à l'entretien de son épouse et qu'il est dit et constaté que l'attribution de la jouissance exclusive du domicile conjugal est devenue sans objet. Il a sollicité la confirmation du jugement querellé pour le surplus. D.c. Par arrêt du 12 février 2016, la Cour de justice a confirmé le jugement entrepris. E. Par acte du 15 mars 2016, A._ interjette un recours en matière civile au Tribunal fédéral contre l'arrêt du 12 février 2016. Il conclut principalement à son annulation en tant qu'il a confirmé les chiffres 6 et 10 du dispositif du jugement de première instance et à sa réforme en ce sens qu'il est condamné à verser en mains de B._ la somme de 200 fr. par mois et d'avance, allocations familiales non comprises, au titre de l'entretien de C._ et ce du 1 er juin 2014 jusqu'au 28 janvier 2015; subsidiairement, il conclut à l'annulation de l'arrêt entrepris en tant qu'il a confirmé les chiffres 6 et 10 du dispositif du jugement de première instance et au renvoi de la cause à l'autorité cantonale pour nouvelle décision au sens des considérants. Il requiert également d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale. Invitées à se déterminer, la Cour de justice s'est référée aux considérants de son arrêt et l'intimée a conclu principalement à l'irrecevabilité du recours et, subsidiairement, à son rejet, sollicitant également d'être mise au bénéfice de l'assistance judiciaire. Le recourant a répliqué le 5 août 2016, persistant dans ses conclusions. L'intimée a renoncé à dupliquer par courrier du 10 août 2016.