Faits: A. X._, ressortissant des Philippines né en 1968 et sa compatriote Y._, née en 1972, ont été interpellés le 8 juin 2008 en situation irrégulière à Genève, dans le cadre d'une intervention policière pour des violences domestiques. Lors de son audition du 9 juin 2008 par la Gendarmerie de Carouge, X._a déclaré être arrivé à Genève le 30 juillet 1998 et y avoir depuis lors séjourné et travaillé sans autorisation. Il a expliqué qu'il avait été engagé par divers employeurs comme homme de ménage ou gardien, qu'il vivait en Suisse avec Y._, mais qu'il avait encore son épouse et sa fille aux Philippines et qu'il était en outre père d'un fils de deux ans, né d'une relation avec une compatriote résidant à Genève, mais dont il ignorait l'adresse. Le 10 septembre 2008, X._ a déposé une demande d'autorisation de séjour. Entendu le 4 novembre 2008 par l'Office cantonal de la population du canton de Genève au sujet de sa situation personnelle, le prénommé a exposé qu'il était venu en Suisse en 1998 et que son fils A._ vivait avec sa mère à Genève. Il a relevé en outre qu'il avait encore un frère et quelques cousins dans son pays, mais qu'il souhaitait rester en Suisse pour des raisons économiques. Il a enfin indiqué qu'il se sentait bien en Suisse, y fréquentait essentiellement des compatriotes, mais qu'il avait commencé de suivre des cours de français en septembre 2008. Le 12 mai 2008, l'employeur de Y._ a déposé pour elle auprès de l'Office cantonal de la population une demande de permis de travail, en précisant que celle-ci travaillait à son service comme employée de maison depuis le mois d'octobre 2007. Lors de son audition du 9 juin 2008 par la Gendarmerie de Carouge, la prénommée a déclaré être arrivée à Genève en septembre 2005 et y avoir ensuite séjourné et travaillé sans autorisation, précisant qu'elle était célibataire, sans enfants et que ses parents et ses sept frères et soeurs vivaient aux Philippines. Elle a expliqué qu'elle formait depuis deux ans et demi un couple avec X._, que celui-ci l'avait certes frappée et menacée lors d'une altercation à leur domicile, mais qu'elle souhaitait lui accorder une seconde chance et n'entendait pas engager une procédure pénale à son encontre. B. Le 27 avril 2009, l'Office cantonal de la population a informé X._ et Y._ de ce qu'il était disposé à leur délivrer une autorisation de séjour en application des art. 30 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr ; RS 142.20) et 31 de l'ordonnance fédérale du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA ; RS 142.201), mais que cette décision demeurait subordonnée à l'approbation de l'Office fédéral des migrations, auquel il soumettait le dossier. Après avoir donné aux prénommés la possibilité de s'exprimer, l'Office fédéral des migrations a refusé, par décisions du 23 juin 2010, d'approuver l'octroi en leur faveur d'une autorisation de séjour en dérogation aux conditions d'admission et de renvoi. Cette autorité a relevé que les intéressés avaient longtemps vécu illégalement en Suisse, ne s'étaient pas créé d'attaches sociales et professionnelles particulièrement étroites avec ce pays, n'y avaient pas suivi de formation particulière et conservaient en réalité des attaches avec leur pays, dans lequel ils avaient passé leur enfance, leur adolescence et une grande partie de leur vie d'adulte et où vivaient encore des membres proches de leur famille. A l'encontre de ces décisions, X._ et Y._ ont conjointement recouru au Tribunal administratif fédéral. Ils ont notamment exposé qu'ils attendaient la naissance de leur premier enfant et que leur éventuel retour aux Philippines les placerait, pour ce motif également, dans une situation économique très difficile, dès lors qu'ils n'y avaient ni maison, ni travail. Le 27 juillet 2010, le Tribunal administratif fédéral a joint les causes. Dans le cadre de l'instruction, X._ a notamment fait valoir qu'il entendait maintenir des relations familiales avec son fils A._, dont la mère bénéficiait d'un "statut durable" en Suisse. X._ et Y._ ont également produit une déclaration écrite de B._, ressortissante philippine et mère de A._, né le 6 novembre 2005, déclaration dans laquelle la prénommée confirmait que X._ entretenait des relations régulières avec son fils, désormais titulaire d'une autorisation de séjour CE/AELE, et qu'il lui versait une pension pour l'entretien de l'enfant. Par arrêt du 26 août 2011, le Tribunal administratif fédéral a rejeté le recours. C. Agissant par la voie du recours en matière de droit public, X._ et Y._ demandent au Tribunal, principalement, d'annuler l'arrêt du Tribunal administratif fédéral et d'approuver l'octroi d'une autorisation de séjour au premier nommé et, en conséquence, à la seconde ; à titre subsidiaire, ils concluent au renvoi de la cause à l'autorité précédente pour complément d'instruction et nouvelle décision, le tout sous suite de frais et dépens. Ils requièrent en outre le bénéfice de l'assistance judiciaire et la désignation de Me Jean-Pierre Garbade comme avocat d'office. L'autorité précédente renonce à se déterminer sur le recours, alors que l'Office fédéral des migrations conclut à son rejet.