Faits: A. A.a A._ est un footballeur professionnel né le 17 mars 1980. X._ Club (ci-après: X._) et Z._ Club (ci-après: Z._) sont deux clubs de football professionnels, membres de la Fédération ..., elle-même affiliée à la Fédération Internationale de Football Association (FIFA). A.b Le 1er octobre 2005, A._ et Z._ ont signé un contrat de travail dont le terme a été fixé au 30 juin 2006. Un nouveau contrat de travail, signé le 5 juin 2006 par les mêmes parties, a prolongé les rapports contractuels liant celles-ci jusqu'au 30 juin 2007. A une date non précisée, le joueur et Z._ ont signé une annexe au second contrat de travail, reportant l'échéance de ce dernier au 30 juin 2009 (ci-après: l'Annexe). Le 24 juin 2007, A._ a signé un contrat de travail avec X._ pour la période du 1er juillet 2007 au 30 juin 2009. Simultanément, X._ a engagé trois autres personnes encore sous contrat avec Z._, dont l'entraîneur de cette équipe. A.c Z._ s'est opposé en vain à ce que A._ fût enregistré comme joueur de X._. S'en est suivie une longue procédure administrative, dans le pays .... Statuant en dernière instance, la Cour de cassation de ce pays, par arrêt du 9 février 2011, a annulé la décision entérinant cet enregistrement. Selon elle, l'Annexe était valable. Dès lors, le joueur, sous contrat avec Z._ jusqu'au 30 juin 2009, avait violé son devoir de fidélité en se faisant engager par X._ avant cette date-là. A.d Le 30 janvier 2008, Z._ a assigné A._ et X._ devant la Chambre de Résolution des Litiges (CRL) de la FIFA en vue d'obtenir leur condamnation solidaire au paiement d'un million de dollars pour rupture injustifiée du contrat, respectivement incitation à une telle rupture, ainsi que des sanctions sportives. Statuant le 6 mai 2010, la CRL, entre autres décisions, a condamné A._ à payer la somme de 400'000 USD à Z._ (ch. 2 du dispositif), reconnu X._ débiteur solidaire de cette somme (ch. 3 du dispositif), suspendu le joueur pour tout match officiel pendant quatre mois à partir du début de la saison à venir (ch. 6 du dispositif) et interdit à X._ de recruter de nouveaux joueurs, à l'échelle nationale et internationale, durant les deux périodes d'enregistrement consécutives à la notification de sa décision (ch. 7 du dispositif). A l'appui de celle-ci, la CRL a retenu, en résumé, que X._ avait incité le joueur à rompre sans juste cause, durant la période protégée, le contrat de travail qui le liait à Z._, comportement qui devait être sanctionné tant au niveau financier que sportif en application de l'art. 17 du Règlement du Statut et du Transfert des Joueurs édicté par la FIFA (RSTJ). B. B.a Le 16 août 2010, X._ a adressé au Tribunal Arbitral du Sport (TAS) une déclaration d'appel, avant de déposer son mémoire d'appel en date du 23 septembre 2012. A._ en a fait de même, les 20 août et 23 septembre 2012. L'un et l'autre a conclu à l'annulation de la décision de la CRL, à sa libération de toute condamnation pécuniaire et à la suppression de la sanction sportive le concernant. Les appelants ont soutenu la thèse selon laquelle le joueur, qui n'avait jamais eu l'intention de prolonger son contrat avec Z._, avait été victime du dol d'un employé de ce club, lequel lui avait présenté l'Annexe comme étant une formalité administrative à remplir en rapport avec l'extinction du contrat. Ils ont affirmé, au sujet de ce document, qu'il était entièrement rédigé en langue ... et que sa version anglaise y avait été insérée après coup. Pour eux, cet état de choses, confirmé par d'autres circonstances, démontrait que le contrat liant le joueur à Z._ avait pris fin le 30 juin 2007, autrement dit un jour avant le début des rapports contractuels noués par A._ avec X._. Par conséquent, de l'avis des appelants, l'art. 17 RSTJ n'était pas applicable en l'espèce. Dans sa réponse du 1er novembre 2010, la FIFA, reprenant à son compte les arguments de la CRL, a conclu au rejet des deux appels et à la confirmation de la décision attaquée. Z._ a pris des conclusions similaires au terme de sa réponse du 8 novembre 2010. Pour lui, les questions relatives à la prétendue tromperie du joueur au moment de la signature de l'Annexe et à la validité de cet avenant avaient été tranchées définitivement par les tribunaux ... dont les décisions étaient revêtues de l'autorité de la chose jugée. Quant à l'Annexe signée par le joueur, elle contenait déjà la version ... et la version anglaise. De surcroît, les appelants, à qui cette preuve incombait, n'avaient pas été en mesure d'établir que le joueur aurait été induit à signer ce document par le dol d'un employé de Z._. Le TAS a joint les deux causes susmentionnées pour instruction et jugement. A la demande des appelants, il a suspendu l'exécution des sanctions disciplinaires prononcées à leur encontre. Donnant suite à une requête de X._, le TAS a ordonné une expertise de l'Annexe. Le TAS a tenu une première audience d'instruction à son siège lausannois le 22 juin 2011. Il a procédé à l'audition du joueur, de l'expert et de plusieurs témoins. Une seconde audience d'instruction s'est déroulée le 10 janvier 2012 à Lausanne. A cette occasion, X._, A._ et Z._ ont annoncé qu'ils avaient conclu un accord transactionnel (ci-après: la Convention) et qu'ils s'étaient en particulier entendus au sujet des faits suivants (ci-après: les Faits admis; traduction libre de l'anglais): - le joueur reconnaît avoir signé l'Annexe sans réaliser ce qu'il était effectivement en train de signer à l'époque; - le joueur a été empêché de jouer pour un autre club durant la saison 2010-2011 en raison du présent litige; - sur la base des preuves fournies par le joueur, Z._ reconnaît que celui-ci a signé l'Annexe sans en comprendre complètement le sens et qu'il n'a pas eu l'intention de violer le contrat de travail les liant ni ne l'a fait; - le joueur confirme que X._ ne l'a pas incité à rompre son contrat de travail le liant à Z._; - Z._ admet que X._ n'a pas incité le joueur à rompre le contrat de travail qui les liait. Etant donné l'existence de la Convention, les signataires de celle-ci ont renoncé à poursuivre l'instruction de la cause. Z._, en particulier, n'a pas fait entendre un certain nombre de témoins qui étaient présents et dont il avait déjà produit un résumé écrit des points sur lesquels ils seraient interrogés. Les conseils des parties à la Convention ont invité la Formation du TAS à tenir compte des Faits admis, tout en reconnaissant qu'elle était libre d'en évaluer le poids au regard des allégations des parties et des autres éléments de preuve déjà recueillis. Pour sa part, la FIFA a demandé à la Formation de ne pas prendre en considération les Faits admis, dans la mesure où ceux-ci étaient incompatibles avec les preuves administrées de même qu'avec les opinions émises par les parties. B.b La Formation a rendu sa sentence le 29 février 2012. Admettant partiellement les deux appels, elle a dit que les chiffres 1 à 5 du dispositif de la décision de la CRL étaient annulés du consentement (ou faute d'objection) de toutes les parties. Pour le surplus, les conclusions des appelants ont été rejetées. Les trois arbitres ont examiné la cause en litige à la lumière de l'art. 17 RSTJ, dans sa version en vigueur au 1er janvier 2008, et, subsidiairement, au regard du droit suisse. Leur principale préoccupation a été de déterminer l'incidence de la Convention sur la procédure d'appel pendante devant eux. A leur avis, Z._, qui avait élevé des prétentions pécuniaires à l'encontre des appelants, était libre d'y renoncer, qu'elles fussent fondées ou non, comme elle l'avait fait en passant cet accord avec le joueur et son nouveau club. Toutefois, la décision de la CRL revêtait un caractère hybride. En effet, à côté de la compensation financière allouée au club demandeur, elle imposait des sanctions sportives aux appelants; dans cette mesure, elle intéressait la FIFA et ceux-ci, mais pas Z._. Les arbitres se sont alors demandé si, via la Convention, c'est-à-dire un accord interne, les parties pouvaient forcer la Formation à accepter la version des faits présentée par elles. Ils ont partagé, sur ce point, la crainte, exprimée par la FIFA, de se voir privée de son pouvoir disciplinaire et, partant, de la faculté de sanctionner les violations du principe cardinal de la fidélité contractuelle, s'il suffisait aux parties de récrire l'histoire sans tenir compte de la réalité des faits. Aussi n'ont-ils pas accepté que les allégations formulées et les preuves administrées pussent être retirées, comme si elles n'avaient jamais existé, par la seule volonté des parties, à plus forte raison du moment que l'une d'elles - en l'occurrence, la FIFA - s'était opposée à ce mode de faire. Et les arbitres de conclure que, s'ils ne pouvaient certes ignorer les Faits admis, ils pouvaient et devaient déterminer l'importance qu'il convenait de leur attribuer dans le contexte de tous les autres éléments de preuve dont ils disposaient. Son pouvoir d'examen fixé, la Formation est entrée en matière. Elle s'est considérée comme liée par l'arrêt de la Cour de cassation, en vertu du principe de l'autorité de la chose jugée, en tant qu'il constatait que l'Annexe n'était pas un faux et que le joueur n'avait pas été incité à la signer par une tromperie touchant la nature et les effets de cet avenant à son contrat de travail. Envisageant, toutefois, la possibilité qu'elle ait pu ne comprendre qu'imparfaitement les effets de la décision ..., la Formation a procédé ensuite à une appréciation des preuves versées au dossier de l'arbitrage. Elle en a déduit, nonobstant les Faits admis, que le joueur avait rompu sans juste cause le contrat qui le liait à Z._ et que son nouveau club n'avait pas réussi à infirmer la présomption, ancrée à l'art. 17 al. 4 RSTJ, selon laquelle il avait poussé ce professionnel à une rupture de contrat. En conclusion, la Formation, après avoir rappelé que le but de l'art. 17 RSTJ est de promouvoir la stabilité contractuelle, a dénié aux parties la faculté d'éluder le régime disciplinaire destiné à assurer la poursuite de cet objectif en cherchant à échapper aux sanctions sportives émanant de l'autorité compétente de la FIFA par le biais d'un accord qui contredit le déroulement des faits à raison desquels ces sanctions ont été prononcées. Elle a néanmoins réservé l'hypothèse, étrangère à la cause en litige, dans laquelle les circonstances censées justifier une sanction sportive se révéleraient erronées ou incomplètes a posteriori, ce dont les parties conviendraient dans un accord approuvé par la FIFA. Les arbitres ont alors repris à leur compte les motifs énoncés dans la décision de la CRL à l'appui des sanctions sportives infligées aux appelants, sanctions qu'ils ont confirmées. C. Le 11 mai 2012, X._ (ci-après: le recourant) a formé un recours en matière civile, assorti d'une demande d'effet suspensif, en vue d'obtenir l'annulation de la sentence du 29 février 2012. En revanche, A._ n'a pas attaqué cette sentence devant le Tribunal fédéral. Par ordonnance présidentielle du 31 mai 2012, le recourant a été invité à verser le montant de 7'000 fr. à la Caisse du Tribunal fédéral en garantie des dépens de la FIFA (ci-après: l'intimée), qui avait présenté une demande ad hoc. Il s'est exécuté en temps utile. Au terme de ses observations du 30 août 2012, le TAS, qui a produit son dossier, a conclu au rejet du recours. L'intimée en a fait de même dans sa réponse du 19 septembre 2012. Quant à Z._, il n'a pas déposé de réponse dans le délai qui lui avait été imparti pour ce faire. Le recourant n'a pas fait usage de la possibilité qui lui avait été donnée de formuler des observations au sujet des réponses du TAS et de l'intimée.