Faits:
A. A.a A._, né en 1971, et dame A._, née en 1973, tous deux de nationalité somalienne, se sont mariés à Mogadishu (Somalie) le 20 mai 1994. Quatre enfants sont issus de cette union: B._, né en 1995, C._, né en 1996, D._, née en 1997, et E._, née en 1998.
L'épouse s'est installée à Genève avec les enfants le 25 juin 1998, où son époux l'a rejointe peu après. Elle est également la mère d'un autre enfant, né en 1991, qui vit avec elle.
A.b Les époux vivent séparés depuis le 18 novembre 2005. Dans le cadre de mesures protectrices de l'union conjugale ordonnées le 2 mars 2006 à la requête de l'épouse, le Tribunal de première instance du canton de Genève a considéré que le revenu mensuel de l'époux (2'298 fr. 60) ne lui permettait pas de s'acquitter d'une contribution d'entretien en faveur de sa famille, compte tenu de son minimum vital élargi de 2'070 fr.
A.c L'épouse travaille comme agente propreté et hygiène auprès de X._ à 75% et réalise un revenu mensuel net moyen de 3'313 fr. 50. Depuis le 1er mars 2008, elle perçoit une aide de l'Hospice général de 1'800 fr. 10 par mois.
L'époux est employé comme technicien au département des gouvernantes de l'hôtel Y._ à 100%; son revenu mensuel net, impôt à la source déduit, s'élève à 2'893 fr. 40, versé treize fois l'an, correspondant à 3'134 fr. 50 sur douze mois.
B. B.a Par jugement du 28 octobre 2009, le Tribunal de première instance de Genève a prononcé le divorce des époux (ch. 1) et, entre autres points, attribué l'autorité parentale et la garde des quatre enfants à la mère (ch. 2), réservé un droit de visite au père (ch. 3), condamné le père à verser une contribution à l'entretien de chacun de ses quatre enfants de 55 fr. par mois, allocations familiales non comprises, jusqu'à leur majorité (ch. 6), dites contributions devant être indexées à l'indice genevois des prix à la consommation, la première fois le 1er janvier 2010 (ch. 8), les époux renonçant par ailleurs à se réclamer réciproquement une contribution à leur propre entretien (ch. 7).
B.b Statuant sur appel de l'épouse, par arrêt du 21 mai 2010, la Cour de justice du canton de Genève a réformé ce jugement en ce sens que le père est condamné à verser, à titre de contribution à l'entretien de chacun de ses quatre enfants, allocations familiales ou d'études éventuelles non comprises, 250 fr. par mois jusqu'à 18 ans, voire au-delà en cas d'études ou de formation professionnelle régulières et suivies, ces contributions devant être indexées à l'indice genevois des prix à la consommation, la première fois le 1er janvier 2011.
C. Le père interjette le 28 juin 2010 un recours en matière civile au Tribunal fédéral contre cet arrêt, concluant à sa réforme en ce sens que le jugement du tribunal de première instance est rétabli. Il fait grief à la cour cantonale de lui avoir imputé un revenu hypothétique supplémentaire de 1'000 fr. par mois, pour le motif qu'il percevrait des pourboires en sus du salaire versé par son employeur. Il requiert en outre l'assistance judiciaire.
L'intimée conclut au rejet du recours et sollicite également le bénéfice de l'assistance judiciaire.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité du recours qui lui est soumis (<ref-ruling> consid. 1.1 p. 3).
1.1 Seul le montant des contributions d'entretien dues par le père en faveur des enfants après divorce est litigieux. L'arrêt entrepris est une décision finale (art. 90 LTF) rendue en matière civile (art. 72 al. 1 LTF) dans une contestation pécuniaire dont la valeur litigieuse atteint 30'000 fr. (art. 51 al. 1 let. a et 74 al. 1 let. b LTF). Le recourant a qualité pour recourir (art. 76 al. 1 LTF), car il a pris part à la procédure devant l'autorité précédente et a un intérêt juridique à la modification de la décision attaquée. Déposé dans le délai (art. 100 al. 1 LTF) et la forme (art. 42 LTF) prévus par la loi, le recours est en principe recevable.
1.2 Le recours en matière civile peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2 p. 550). Compte tenu des exigences de motivation posées, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), à l'art. 42 al. 2 LTF, le Tribunal fédéral n'examine en principe que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une juridiction de première instance, toutes les questions juridiques pouvant se poser lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 1.2 p. 152).
1.3 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF), et si la correction du vice est susceptible d'influencer le sort de la cause (art. 97 al. 1 LTF). Le recourant qui soutient que les faits ont été établis de manière manifestement inexacte (art. 97 al. 1 LTF), à savoir que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation. Le Tribunal fédéral n'examine en effet la violation de l'interdiction de l'arbitraire que si ce grief a été invoqué et motivé par le recourant (art. 106 al. 2 LTF), c'est-à-dire s'il a été expressément soulevé et exposé de façon claire et détaillée (principe d'allégation; <ref-ruling> consid. 1.4 p. 287).
2. En appel, la mère a soutenu que la situation financière du père avait été mésestimée par le Tribunal de première instance, celui-là recevant des pourboires de l'ordre de 1'000 fr. par mois dans le cadre de son activité de portier dans un hôtel de luxe; le père a contesté ce fait, pour le motif qu'il n'avait pas de contacts avec la clientèle de l'hôtel. La cour cantonale a rappelé qu'un débirentier peut se voir imputer un revenu hypothétique supérieur à celui qu'il obtient effectivement, pour autant qu'une telle augmentation soit possible et qu'elle puisse raisonnablement être exigée de lui. En l'espèce, selon l'attestation de travail produite par le père, celui-ci est certes employé en qualité de "technicien au Département des gouvernantes" de l'hôtel Y._; néanmoins, son employeur a également loué son comportement toujours extrêmement correct, sa politesse, sa flexibilité, son caractère agréable, son honnêteté ainsi que sa bonne présentation, qualités que l'on recherche, selon la cour cantonale, chez un employé qui a un contact avec la clientèle, ce qui constitue un indice que tel est le cas. A cela s'ajoute qu'à l'audience de comparution personnelle du 16 février 2009, le père a indiqué qu'il était portier d'étage. Or, selon les juges précédents, il est constant que l'activité de portier d'étage comporte des services à la clientèle, notamment le transport des bagages, qui le mettent en contact direct avec les clients, et qu'elle est donc susceptible de lui permettre de recevoir des pourboires. Enfin, le père s'acquitte d'un loyer mensuel de 1'372 fr., ce qui est difficilement compatible avec un revenu de 3'134 fr. 50, puisque cela correspond à 43% de celui-ci. Sur la base de ces indices, la cour cantonale a considéré que le père réalise un revenu supérieur à celui retenu par le Tribunal de première instance, par le biais de pourboires qu'il reçoit dans le cadre de son activité. Le montant articulé par la mère, de 1'000 fr. par mois, paraît réaliste pour une activité à temps plein dans un hôtel du standing de celui dans lequel le père travaille. Ses revenus mensuels nets ont donc été évalués à 4'134 fr., alors que ses charges mensuelles incompressibles s'élèvent au total à 3'013 fr. 60, à savoir 1'372 fr. de loyer, 371 fr. 60 d'assurance-maladie, 70 fr. de frais de transport et 1'200 fr. de minimum vital. Le père dispose ainsi d'un solde disponible de 1'120 fr. 40, lui permettant de contribuer partiellement à l'entretien de ses enfants, à hauteur de 250 fr. par mois et par enfant.
3. Le recourant fait grief à la cour cantonale d'avoir retenu comme avéré, malgré sa contestation formelle et l'absence de tout moyen de preuve à l'appui, que son revenu mensuel dépasse celui déclaré par l'employeur de 1'000 fr., à savoir d'un montant "hypothétique" correspondant à des pourboires qu'il toucherait des clients de l'hôtel où il travaille. Selon lui, il est inconcevable de déduire des termes figurant dans le certificat intermédiaire de travail délivré par son employeur qu'il est en contact avec la clientèle. Ce certificat précise clairement que son activité est du domaine "technique" et ne mentionne pas de contacts avec les clients, qui nécessitent, au demeurant, une maîtrise des langues qu'il n'a pas. Son activité consiste en la mise à disposition des employés de matériel, de linge et de produits utiles à la préparation des chambres et "l'occupation des espaces douches et WC de divers produits". S'agissant du montant consacré à son loyer, les juges précédents auraient omis de prendre en considération l'état de pénurie de logement qui frappe Genève. Un loyer de 1'372 fr. pour un appartement de 4,5 pièces à Genève serait plus que raisonnable, respectivement au-dessous de la moyenne actuelle sur le marché cantonal immobilier, le recourant n'ayant pu obtenir cet appartement, proche du domicile de l'intimée, que grâce à l'intervention massive des services sociaux. En outre, s'il souhaite exercer son droit de visite dans des conditions acceptables pour ses quatre enfants, notamment pouvoir les garder la nuit, le recourant doit accepter de sacrifier 43% de son revenu au loyer, ne pouvant espérer, avec son revenu mensuel de 2'800 fr. net par mois, mieux que son logement actuel. Il serait enfin "hors de toute logique", selon lui, de déduire un salaire hypothétique stable de 1'000 fr. par mois, cela pour plusieurs années à l'avance, en se basant uniquement sur les allégations de l'intimée, alors qu'il s'agit d'un élément très aléatoire, cela supposant que son contact avec la clientèle s'avérerait possible; il est admis que les pourboires varient selon les saisons, les heures de travail effectuées, la fréquence du contact avec la clientèle, ainsi que la "qualité" et la provenance de celle-ci. Or aucun de ces critères n'a été abordé ou pris en considération par les juges précédents, qui se sont contentés d'un raisonnement sommaire pour retenir un revenu hypothétique dépassant un quart du revenu prouvé par pièces du recourant.
4. L'intimée soutient que la cour cantonale a imputé à bon droit un revenu hypothétique de 1'000 fr. supplémentaire au recourant, que celui-ci serait à même de réaliser en faisant preuve de bonne volonté: d'une part, les qualités professionnelles qui sont les siennes lui ouvriraient les portes d'autres emplois, notamment dans le secteur public; d'autre part, il aurait la capacité de percevoir des pourboires dans son activité actuelle de portier d'étage.
5. 5.1 Contrairement à ce que retient l'arrêt attaqué, le revenu supplémentaire imputé au recourant du fait qu'il recevrait des pourboires des clients de l'hôtel où il travaille ne constitue pas un revenu hypothétique - à savoir un revenu qu'il pourrait réaliser en faisant preuve de bonne volonté et en accomplissant un effort que l'on peut raisonnablement exiger de lui -, mais un revenu effectif, que la cour cantonale a admis qu'il réalisait malgré ses dénégations à cet égard. L'argumentation de l'intimée, relative au fait que le recourant pourrait gagner davantage que son salaire actuel en changeant de travail - ce que l'arrêt attaqué ne retient pas -, est nouvelle et, faute d'épuisement des instances cantonales (art. 75 al. 1 LTF), irrecevable (<ref-ruling> consid. 1.3 p. 527).
5.2 Déterminer quel est le revenu effectif d'une partie est une question de fait, que le Tribunal fédéral ne peut revoir que si elle a été établie de manière arbitraire, à savoir manifestement inexacte (cf. supra, consid. 1.3). En l'espèce, la déduction opérée par les juges précédents - sur la seule base des qualités professionnelles du recourant figurant dans son certificat de travail, du fait qu'il ait déclaré être portier d'étage et du montant de son loyer - est insoutenable. Ces éléments apparaissent insuffisants pour que l'on retienne, malgré la contestation formelle du recourant, qu'il a un contact avec la clientèle et perçoit des pourboires à hauteur de 1'000 fr. par mois. Dans la mesure où la contribution d'entretien en faveur des enfants est litigieuse, la maxime inquisitoire est toutefois applicable (art. 145 al. 1 CC); il appartenait ainsi aux juges précédents d'instruire cette question, ceux-ci ne pouvant se contenter, sans commettre d'arbitraire, des quelques indices mentionnés dans l'arrêt attaqué pour considérer que le recourant réalise, tant sur le principe que sur le montant, un revenu de 1'000 fr. plus élevé que celui déclaré. Par conséquent, la cause sera renvoyée à la cour cantonale pour instruction complémentaire sur ce point et nouveau jugement.
6. Vu ce qui précède, le recours est admis et la cause doit être renvoyée à la cour cantonale pour nouvelle décision dans le sens des considérants qui précèdent. L'indigence des deux parties est établie et leurs requêtes d'assistance judiciaire doivent être admises. Me Ridha Ajmi est désigné comme avocat d'office du recourant et Me Françoise Arbex comme avocate d'office de l'intimée; il leur est alloué une indemnité de 1'500 fr. chacun à titre d'honoraires (art. 64 al. 2 LTF). Les frais judiciaires seront mis à la charge de l'intimée, qui succombe (art. 66 al. 1 LTF), mais provisoirement supportés par la Caisse du Tribunal fédéral.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision dans le sens des considérants.
2. La requête d'assistance judiciaire du recourant est admise.
3. La requête d'assistance judiciaire de l'intimée est admise.
4. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge de l'intimée, mais ils sont provisoirement supportés par la Caisse du Tribunal fédéral.
5. Me Ridha Ajmi est désigné en tant qu'avocat d'office du recourant et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires, supportée par la caisse du Tribunal.
6. Me Françoise Arbex est désignée en tant qu'avocate d'office de l'intimée et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires, supportée par la caisse du Tribunal.
7. Le présent arrêt est communiqué aux parties et à la Chambre civile de la Cour de justice du canton de Genève.
Lausanne, le 27 octobre 2010
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Aguet