Faits : A. A.a. A.A._, né en 1962 à Tunis (Tunisie) et B.A._, née en 1970 à Annaba (Algérie), tous deux de nationalité suisse, se sont mariés le 19 octobre 1999 à Genève. Trois enfants sont issus de cette union, à savoir C._ (2000), D._ (2001) et E._ (2003). Les époux se sont séparés le 1 er septembre 2014. B.A._ est restée dans l'appartement familial avec les enfants, tandis que A.A._ a déménagé. A.b. A.A._ exerce la profession de chauffeur de taxi indépendant. Un revenu mensuel contesté de 4'500 fr. lui a été imputé. Ses charges mensuelles ont été arrêtées à 2'690 fr. B.A._ est employée à temps partiel par G._ et a perçu à ce titre un revenu mensuel net moyen de 2'270 fr. en 2014. Ses charges mensuelles ont été arrêtées à 2'458 fr. Les charges mensuelles des trois enfants s'élèvent à 1'410 fr. au total, une fois déduites les allocations familiales perçues par leur mère. B. B.a. Le 12 décembre 2014, A.A._ a déposé une requête de mesures protectrices de l'union conjugale par-devant le Tribunal de première instance du canton de Genève (ci-après: Tribunal). B.b. Le 28 janvier 2015, B.A._ a déposé une requête de mesures superprovisionnelles tendant à la condamnation de son époux à verser une contribution à l'entretien de la famille. Cette requête a été rejetée par ordonnance du 29 janvier 2015. B.c. Par jugement du 15 octobre 2015, le Tribunal a notamment autorisé les époux à vivre séparés (ch. 1 du dispositif), attribué à B.A._ la jouissance exclusive du domicile conjugal (ch. 2), ainsi que la garde sur leurs trois enfants (ch. 3), réservé à A.A._ un droit aux relations personnelles sur ses trois enfants, devant s'exercer d'entente entre lui et ces derniers (ch. 4), condamné A.A._ à payer en mains de B.A._, à titre de contribution à l'entretien des trois enfants, par mois, d'avance et par enfant, allocations familiales non comprises, la somme de 450 fr. à compter du prononcé du jugement (ch. 5) et condamné en tant que de besoin les parties à respecter et à exécuter les dispositions du jugement (ch. 10). B.d. Par actes du 2 novembre 2015, les parties ont toutes deux fait appel de ce jugement par-devant la Cour de justice du canton de Genève (ci-après: Cour de justice). B.d.a. A.A._ a conclu à l'annulation des chiffres 4 et 5 du dispositif du jugement précité et à leur réforme en ce sens qu'un droit de visite progressif sur ses trois enfants lui est accordé, sous la surveillance du Service de protection des mineurs (SPMi), dans le cadre d'une curatelle au sens de l'art. 308 al. 2 CC, selon les modalités suivantes: un jour toutes les deux semaines durant deux mois, une nuit toutes les deux semaines les deux mois suivants et un week-end sur deux et la moitié des vacances scolaires. Il a également conclu à ce qu'il lui soit donné acte de son engagement de payer en mains de B.A._, à titre de contribution d'entretien pour ses trois enfants, par mois, d'avance et par enfant, allocations familiales non comprises, la somme de 150 fr., soit un total de 450 fr. B.A._ a conclu au rejet de l'appel de son époux, avec suite de frais et dépens. B.d.b. B.A._ a conclu à l'annulation et à la réforme du chiffre 5 du dispositif du jugement attaqué. Elle a conclu principalement à l'attribution de l'autorité parentale exclusive et a sollicité le versement d'une contribution pour l'entretien de la famille de 2'400 fr., allocations familiales non comprises, depuis le 12 décembre 2014. Subsidiairement, elle a conclu à la condamnation de A.A._ à verser, en ses mains, par mois et par avance, depuis le 12 décembre 2014, 650 fr. pour l'entretien de chaque enfant, allocations familiales non comprises, et 450 fr. pour son propre entretien. Plus subsidiairement, elle a conclu à la condamnation de A.A._ à verser, en ses mains, par mois et par avance, depuis le 12 décembre 2014, 450 fr. pour l'entretien de chaque enfant, allocations familiales non comprises, et 950 fr. pour son propre entretien. Dans sa réponse du 20 novembre 2015, A.A._ a conclu principalement au rejet de l'appel, avec suite de frais et dépens. Subsidiairement, il a sollicité une expertise familiale ou un rapport du SPMi sur la question de l'attribution de l'autorité parentale. B.e. Par arrêt du 11 mars 2016, expédié le 14 mars 2016, la Cour de justice a annulé les chiffres 4, 5 et 10 du dispositif du jugement entrepris et les a réformés en ce sens qu'elle a attribué à B.A._ l'autorité parentale exclusive sur les trois enfants, dit qu'il n'y avait pas lieu de fixer de droit de visite en faveur de A.A._ et condamné ce dernier à verser en mains de B.A._, par mois et d'avance, allocations familiales non comprises, à compter du 28 janvier 2015, une contribution d'entretien de 230 fr. en faveur de son épouse et de 500 fr. en faveur de chacun des trois enfants, sous déduction d'un montant unique de 300 fr. C. Par acte du 14 avril 2016, A.A._ interjette un recours en matière civile au Tribunal fédéral contre cet arrêt. Il conclut principalement à son annulation et à sa réforme en ce sens que l'autorité parentale conjointe est instaurée, qu'il lui est donné acte de son engagement à verser un montant mensuel de 150 fr. à titre de contribution à l'entretien de chacun de ses trois enfants et qu'il est dit que ces contributions d'entretien ne sont pas assorties de l'effet rétroactif. Subsidiairement, il conclut au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il requiert également que son recours soit muni de l'effet suspensif et d'être mis au bénéfice de l'assistance judiciaire pour la procédure fédérale. Invitée à se déterminer sur la requête d'effet suspensif assortissant le recours, B.A._ a conclu à son rejet. Elle a également sollicité d'être mise au bénéfice de l'assistance judiciaire pour la procédure fédérale. Des déterminations au fond n'ont pas été requises. D. Par ordonnance présidentielle du 28 avril 2016, l'effet suspensif a été accordé pour les contributions d'entretien dues jusqu'au 31 mars 2016 mais non pour les montants dus à partir du 1 er avril 2016.