Faits: A. A.X._ et B.Z._, tous deux nés en 1969, sont unis par un mariage coutumier. Ils ont quatre enfants, C.X._, né en 1988, D.X._, né en 1990, E.X._, née en 1992 et F.X._, né en 1994. En janvier 1999, A.X._ est entré en Suisse pour y déposer une demande d'asile. Il a indiqué être de nationalité yougoslave et a remis aux autorités helvétiques la copie d'un passeport de l'ex-République fédérale de Yougoslavie établi à son nom. Le 3 mars 1999, l'Office fédéral des réfugiés (actuellement Office fédéral des migrations: ODM) a rendu une décision de non-entrée en matière sur la demande d'asile de A.X._ et a prononcé le renvoi de celui-ci de Suisse. Le 7 janvier 2004, A.X._ et B.Z._ ont rempli un rapport d'arrivée à l'attention de l'autorité vaudoise de police des étrangers, indiquant être entrés en Suisse le 5 janvier 2004 avec leurs quatre enfants en provenance de Macédoine et n'être en possession d'aucune pièce de légitimation; ils ont affirmé être apatrides. Le 23 mars 2004, A.X._ et B.Z._ ont déposé une demande de reconnaissance du statut d'apatrides auprès de l'ODM. A l'appui de leur requête, ils ont produit divers documents, notamment, concernant A.X._, les copies d'un extrait de registre de naissance émanant des autorités de la République de Macédoine, d'une attestation de la République de Serbie du 4 juillet 2002 certifiant que celui-ci n'était pas citoyen de cette République ni de la République fédérale de Yougoslavie et d'une décision du Ministère macédonien de l'intérieur du 30 juillet 2002 prononçant le rejet d'une demande de résidence et de naturalisation; pour B.Z._ et les 4 enfants, des copies d'extraits d'actes de naissance établis en 1997 à Prizren et en 2003 et 2004 à Vrsac, par les autorités de l'ex-République fédérale de Yougoslavie ont été remises. La famille a également transmis des copies de lettres de l'Ambassade de la République de Macédoine à Bonn du 2 juin 2000 indiquant, pour chacun de ses membres, ne pas pouvoir délivrer un document de voyage, car ceux-ci n'avaient pas la nationalité de cet Etat. Le 28 juin 2004, l'ODM a indiqué que le Corps des gardes frontières de Bâle avait intercepté, en décembre 2003, un envoi postal en provenance d'Allemagne dans lequel se trouvait l'original d'un passeport provisoire macédonien, la copie d'un autre passeport établi en décembre 2002, la copie d'un passeport yougoslave et un acte de naissance macédonien. Comme ces documents, établis au nom de A.X._, ne paraissaient pas avoir été falsifiés, l'ODM a communiqué aux intéressés qu'il envisageait de ne pas entrer en matière sur leur demande tendant à la reconnaissance du statut d'apatrides. Les requérants ont eu l'occasion de se prononcer sur ces documents. Ils ont relevé qu'ils accréditaient leur thèse selon laquelle ils avaient été ballottés d'un pays à l'autre, les autorités de Serbie et de Macédoine refusant de les reconnaître comme leurs ressortissants. L'ODM a procédé à diverses investigations, demandant la collaboration de la Représentation suisse à Skopje. Il a obtenu en particulier la copie d'un acte de naissance et d'un acte de citoyenneté délivrés par les autorités de Skopje, au nom de A.X._ le 14 mars 2005. Les requérants ont pu se déterminer. Estimant que l'état de fait n'était pas suffisamment établi, ils ont précisé à l'attention de l'ODM qu'ils s'étaient adressés, le 11 mai 2005, au Ministère macédonien des affaires intérieures dans le but d'être formellement admis à vivre à Skopje, de pouvoir y bénéficier d'un appartement et des moyens d'existence nécessaires. Ils priaient l'ODM de bien vouloir s'enquérir auprès des autorités macédoniennes de la suite qu'elles entendaient donner à leur requête. B. Par décision du 27 juin 2005, l'ODM a rejeté la demande tendant à considérer A.X._ et sa famille comme des apatrides. Il a retenu en bref qu'il ne résultait pas des pièces du dossier que les intéressés avaient été privés de leur nationalité et qu'ils ne pourraient la recouvrer. L'acte de naissance et de citoyenneté établis au nom de A.X._ en mars 2005 en fournissaient la preuve. Quant à B.Z._ et les quatre enfants, les actes de naissance datant de 1997, 2003 et 2004 reçus des autorités de Prizren et Vrsac leur permettaient de se faire établir des actes de citoyenneté desdites autorités. Le recours contre cette décision, déposé le 14 juillet 2005 auprès du Département fédéral de justice et police, a été transmis au Tribunal administratif fédéral le 1er janvier 2007. C. Par arrêt du 21 novembre 2007, le Tribunal administratif fédéral a rejeté le recours. Il a jugé qu'au vu des exigences strictes régissant la reconnaissance du statut d'apatrides, les documents versés au dossier ne suffisaient pas à démontrer que les recourants avaient perdu leur nationalité antérieure ou qu'ils avaient accompli toutes les démarches que l'on pouvait attendre d'eux pour la recouvrer. D. Agissant par la voie du recours en matière de droit public, A.X._, B.Z._ et leurs enfants C.X._, D.X._, E.X._ et F.X._ concluent, avec suite de frais et dépens, à la réforme de l'arrêt du Tribunal administratif fédéral du 21 novembre 2007, en ce sens que le statut d'apatrides leur est reconnu ou, subsidiairement au renvoi de la cause pour nouvelles instruction et décision en ce qui concerne A.X._. Très subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause pour nouvelles instruction et décision. Ils demandent le bénéfice de l'assistance judiciaire. Avec leur recours, ils produisent une attestation de l'Ambassade de Serbie à Berne du 27 décembre 2007, certifiant que, dans la mesure où les intéressés ne possèdent pas un certificat de nationalité serbe depuis six mois au maximum, ils ne peuvent pas obtenir un passeport de la République de Serbie. Le Tribunal administratif fédéral renonce à se déterminer et l'ODM propose le rejet du recours en se référant à sa décision du 27 juin 2005. Le 9 janvier 2008, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif formée par les recourants. 