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.

Considérant en droit:
1. D'après l'art. 54 al. 1 LTF, le Tribunal fédéral rédige son arrêt dans une langue officielle, en règle générale dans la langue de la décision attaquée. Lorsque cette décision est rédigée dans une autre langue (ici l'anglais), le Tribunal fédéral utilise la langue officielle choisie par les parties. Devant le TAS, celles-ci ont utilisé l'anglais et le français. Dans le mémoire qu'il a adressé au Tribunal fédéral, le recourant a employé le français. La réponse de la FIFA, intimée, a été rédigée en allemand. Conformément à sa pratique, le Tribunal fédéral adoptera la langue du recours et rendra, par conséquent, son arrêt en français.
2. Dans le domaine de l'arbitrage international, le recours en matière civile est recevable contre les décisions de tribunaux arbitraux aux conditions fixées par les art. 190 à 192 LDIP (art. 77 al. 1 LTF). Qu'il s'agisse de l'objet du recours, de la qualité pour recourir, du délai de recours, des conclusions prises par le recourant ou encore des griefs soulevés dans le mémoire de recours, aucune de ces conditions de recevabilité ne fait problème en l'espèce. Rien ne s'oppose donc à l'entrée en matière.
3. En premier lieu, le recourant fait grief à la Formation d'avoir méconnu le principe de la fidélité contractuelle et, partant, d'avoir rendu une sentence incompatible avec l'ordre public matériel.
3.1 L'examen matériel d'une sentence arbitrale internationale, par le Tribunal fédéral, est limité à la question de la compatibilité de la sentence avec l'ordre public (<ref-ruling> consid. 3a).
Une sentence est incompatible avec l'ordre public si elle méconnaît les valeurs essentielles et largement reconnues qui, selon les conceptions prévalant en Suisse, devraient constituer le fondement de tout ordre juridique (<ref-ruling> consid. 2.2.3). Elle est contraire à l'ordre public matériel lorsqu'elle viole des principes fondamentaux du droit de fond au point de ne plus être conciliable avec l'ordre juridique et le système de valeurs déterminants; au nombre de ces principes figure la fidélité contractuelle, rendue par l'adage latin pacta sunt servanda.
Le principe pacta sunt servanda, au sens restrictif que lui donne la jurisprudence relative à l'art. 190 al. 2 let. e LDIP, n'est violé que si le tribunal arbitral refuse d'appliquer une clause contractuelle tout en admettant qu'elle lie les parties ou, à l'inverse, s'il leur impose le respect d'une clause dont il considère qu'elle ne les lie pas. En d'autres termes, le tribunal arbitral doit avoir appliqué ou refusé d'appliquer une disposition contractuelle en se mettant en contradiction avec le résultat de son interprétation à propos de l'existence ou du contenu de l'acte juridique litigieux. En revanche, le processus d'interprétation lui-même et les conséquences juridiques qui en sont logiquement tirées ne sont pas régis par le principe de la fidélité contractuelle, de sorte qu'ils ne sauraient prêter le flanc au grief de violation de l'ordre public. Le Tribunal fédéral a souligné à maintes reprises que la quasi-totalité du contentieux dérivé de la violation du contrat est exclue du champ de protection du principe pacta sunt servanda (arrêt 4A_150/2012 du 12 juillet 2012 consid. 5.1 et les arrêts cités).
3.2 Selon le recourant, les arbitres, tout en admettant le caractère contraignant de la Convention pour décider du sort des prétentions pécuniaires élevées par Z._, auraient refusé, de manière contradictoire, de tenir compte de celle-ci pour la question des sanctions sportives. Ils auraient d'ailleurs mal interprété l'art. 17 al. 4 RSTJ en considérant que les sanctions sportives prononcées par la FIFA seraient indépendantes de l'octroi d'éventuelles indemnités au club demandeur.
En argumentant de la sorte, le recourant méconnaît totalement la jurisprudence susmentionnée relative à l'ordre public matériel. D'après le résumé de la sentence attaquée, effectué plus haut (cf. let. B.b), la Formation s'est dite liée par la Convention dans la mesure où la décision de la CRL portait sur l'indemnité allouée à Z._; en conséquence, elle a admis les appels sur ce point sans en examiner les mérites. En revanche, refusant de se voir imposer la Convention en tant que ladite décision avait trait aux sanctions sportives infligées aux appelants, les arbitres ont procédé eux-mêmes au libre examen de la situation, en fait comme en droit, sous cet angle, ce qui les a conduits à entériner ces sanctions en dépit des Faits admis. Ainsi, non seulement on ne décèle aucune incohérence intrinsèque dans les considérants de la sentence entreprise - vice qui n'entrerait pas, du reste, dans la définition de l'ordre public matériel (arrêt 4A_150/2012, précité, consid. 5.2.1) -, mais encore il appert de ce qui précède que chacune des deux conclusions opposées tirées par la Formation correspond à la prémisse dont elle découle. Aussi bien, une éventuelle violation de l'ordre public matériel n'aurait pu être envisagée, en l'espèce, que si la Formation avait confirmé les sanctions sportives contestées tout en admettant qu'elle n'était pas en droit de s'écarter de la Convention, quel que fût l'objet du litige. Pour le surplus, le Tribunal fédéral, lorsqu'il se prononce sur la violation de l'ordre public matériel dans le cadre d'un recours en matière d'arbitrage international, n'a pas à vérifier si le TAS a fait une application correcte de la réglementation sportive applicable.
Le moyen pris de la violation de l'ordre public matériel tombe ainsi manifestement à faux.
4. En deuxième lieu, le recourant reproche aux arbitres d'avoir porté atteinte à l'ordre public procédural.
4.1 L'ordre public procédural, au sens de l'art. 190 al. 2 let. e LDIP, garantit aux parties le droit à un jugement indépendant sur les conclusions et l'état de fait soumis au Tribunal arbitral d'une manière conforme au droit de procédure applicable; il y a violation de l'ordre public procédural lorsque des principes fondamentaux et généralement reconnus ont été violés, ce qui conduit à une contradiction insupportable avec le sentiment de la justice, de telle sorte que la décision apparaît incompatible avec les valeurs reconnues dans un Etat de droit (<ref-ruling> consid. 2.2.1). Au demeurant, l'ordre public procédural n'est qu'une garantie subsidiaire et constitue, à ce titre, une norme de précaution pour les vices de procédure auxquels le législateur n'aurait pas songé en adoptant les autres lettres de l'art. 190 al. 2 LDIP (<ref-ruling> consid. 2.3).
4.1 L'ordre public procédural, au sens de l'art. 190 al. 2 let. e LDIP, garantit aux parties le droit à un jugement indépendant sur les conclusions et l'état de fait soumis au Tribunal arbitral d'une manière conforme au droit de procédure applicable; il y a violation de l'ordre public procédural lorsque des principes fondamentaux et généralement reconnus ont été violés, ce qui conduit à une contradiction insupportable avec le sentiment de la justice, de telle sorte que la décision apparaît incompatible avec les valeurs reconnues dans un Etat de droit (<ref-ruling> consid. 2.2.1). Au demeurant, l'ordre public procédural n'est qu'une garantie subsidiaire et constitue, à ce titre, une norme de précaution pour les vices de procédure auxquels le législateur n'aurait pas songé en adoptant les autres lettres de l'art. 190 al. 2 LDIP (<ref-ruling> consid. 2.3).
4.2 4.2.1 Le recourant impute, tout d'abord, à la Formation une violation du "principe de l'unité de fait", motif pris de ce qu'elle se serait basée sur les circonstances retenues dans la Convention pour entériner le retrait des prétentions pécuniaires élevées par Z._, puis s'en serait écartée pour confirmer les sanctions sportives prononcées par la CRL.
Le grief invoqué ne consiste qu'en une présentation, sous un autre angle, de la critique similaire formulée antérieurement à l'appui du moyen fondé sur la violation de l'ordre public matériel. En le soulevant derechef au titre de la violation de l'ordre public procédural, le recourant méconnaît le caractère subsidiaire de cette garantie.
Par ailleurs, le recourant ne démontre d'aucune façon en quoi le principe de l'unité de fait, dont il ne donne pas la définition ni ne précise le contenu, constituerait un principe fondamental et généralement reconnu. Il ne se réfère pas davantage à une jurisprudence qui aurait cerné cette notion.
Pour le surplus, la prémisse du raisonnement tenu par le recourant est erronée, ainsi que le relève avec raison l'intimée. Le TAS, en effet, ne s'est pas fondé sur les Faits admis pour rendre sa sentence: d'une part, il a vu dans la Convention une renonciation de Z._ à l'indemnité que ce club avait requise et obtenue en première instance, et il a pris acte de cette renonciation sans examiner les faits qui la motivaient; d'autre part, il s'est affranchi des Faits admis pour rechercher lui-même s'il existait des circonstances justifiant de sanctionner les appelants sur le plan sportif.
4.2.2 A suivre le recourant, les parties auraient retiré l'ensemble des arguments, contre-arguments et preuves qu'elles avaient soumis au TAS, de même que leurs prétentions, pour conclure conjointement à l'annulation de la décision prise par la CRL. Dès lors, en ignorant la position adoptée par elles dans la procédure d'appel, la Formation aurait méconnu la maxime des débats et la maxime de disposition, que le recourant déduit respectivement de l'art. R51 du Code de l'arbitrage en matière de sport (ci-après: le Code) et de l'art. 190 al. 2 let. c LDIP, ainsi que l'art. R55 du Code, dans sa version modifiée avec effet au 1er janvier 2010, en tant qu'il ne prévoit plus la possibilité de déposer une demande reconventionnelle. Ces arguments n'apparaissent pas plus fondés que le précédent.
Le recourant ne démontre pas pourquoi il se justifierait de rattacher la maxime des débats à l'ordre public procédural. Quant à la violation d'une disposition du règlement d'arbitrage liant les parties, tel l'art. R51 du Code, elle ne constitue pas un motif d'annulation de la sentence au titre de l'art. 190 al. 2 let. e LDIP (<ref-ruling> consid. 1a p. 347; arrêt 4A_612/2009 du 10 février 2010 consid. 6.3.1).
Pour ce qui est de la maxime de disposition, le recourant la rattache lui-même à une autre lettre de l'art. 190 al. 2 LDIP, si bien qu'il n'y a pas matière à faire intervenir ici la garantie subsidiaire que constitue l'ordre public procédural. Quoi qu'il en soit, la Formation retient que tous les conseils des parties à la Convention ont accepté que les arbitres puissent apprécier eux-mêmes le poids des Faits admis en les replaçant dans le contexte des allégations des parties et des preuves déjà administrées (cf. sentence, nos 60 et 78). Or, il s'agit là d'une constatation relative au déroulement de la procédure arbitrale qui lie le Tribunal fédéral (arrêt 4A_682/2011 du 31 mai 2012 consid. 2.4 et les précédents cités) et que le recourant tente, dès lors, en vain de remettre en cause. De plus, il est constant que l'intimée, qui revêtait sans conteste la qualité de partie à la procédure d'appel, s'est opposée à ce que la Formation se tînt pour liée par les Faits admis. Dans ces conditions, les arbitres ne sauraient se voir reprocher de s'être écartés des faits mentionnés dans la Convention lors de leur examen du bien-fondé des sanctions sportives infligées aux appelants.
Quant au grief, fait à la Formation, de n'avoir pas appliqué l'art. R55 du Code dans sa teneur au 1er janvier 2010, il ne saurait prospérer. En effet, quoi qu'en dise le recourant, l'intimée n'a pas pris une conclusion active à son encontre en invitant simplement le TAS à rejeter les appels et à confirmer la décision attaquée. Elle n'a donc pas formé une demande reconventionnelle, ce faisant.
Enfin, de l'avis du recourant, on ne saurait admettre, sans créer un sentiment choquant d'injustice, que le TAS puisse rendre une décision allant à l'encontre des faits explicitement reconnus dans un accord transactionnel par la partie sans laquelle la FIFA n'aurait jamais procédé contre le joueur et le club défendeurs. Selon lui, pareille situation serait comparable au retrait d'une plainte pénale visant une infraction non poursuivie d'office, retrait qui lie le juge. Cependant, on ne voit pas non plus comment rattacher cette partie de l'argumentation du recourant à la notion d'ordre public procédural, telle qu'elle a été définie par la jurisprudence fédérale. De toute façon, il convient de garder à l'esprit la spécificité de l'art. 17 RSTJ, lequel établi, d'une part, le droit du club lésé de réclamer au joueur ayant rompu le contrat sans juste cause ainsi qu'à son nouveau club une indemnité dont ils seront solidairement redevables envers lui, et, d'autre part, le pouvoir de la FIFA d'infliger des sanctions sportives non seulement au joueur et au club incriminés, mais encore, le cas échéant, à toutes les personnes soumises aux statuts et règlements édictés par elle (officiels, agents de joueurs, etc.) qui ont agi de manière à provoquer la rupture du contrat, en vue de faciliter le transfert du joueur (cf. art. 17 al. 5 RSTJ). La norme réglementaire précitée se caractérise donc par un double aspect, à la fois indemnitaire et disciplinaire. Or, si le premier élément relève de la libre disposition du club demandeur et des parties défenderesses (i.e. le joueur recherché et son nouveau club), tel n'est pas le cas du second qui fait intervenir une tierce partie, à savoir la FIFA en sa qualité de personne morale titulaire du pouvoir disciplinaire et compétente pour prononcer les sanctions sportives prévues à l'art. 17 RSTJ. De ce point de vue, la comparaison faite par le recourant avec une infraction poursuivie uniquement sur plainte du lésé n'a pas sa place ici. A cet égard, l'un des buts statutaires assignés à cette association, qui est de veiller au respect des règles fixées par elle, serait mis en péril si l'on tolérait que, sans le consentement de la FIFA, les parties en litige puissent s'arroger le pouvoir de faire que ce qui fut n'ait pas été, c'est-à-dire construire un nouvel état de fait qui exclurait l'existence, pourtant établie, d'une rupture injustifiée du contrat de travail. Demeure réservée l'hypothèse, énoncée par le TAS, dans laquelle les circonstances retenues pour justifier les sanctions infligées au joueur et à son nouveau club se révéleraient erronées ultérieurement de l'avis unanime des parties et de la FIFA. Dans cette hypothèse, rien ne s'opposerait à ce que celle-ci avalisât un accord des parties constatant la chose et consentît à l'annulation des sanctions prononcées. Toutefois, ce cas de figure est étranger à la présente cause. C'est dire que le sentiment choquant d'injustice exprimé par le recourant n'est pas de mise ici. Ce qui suscite au contraire une certaine perplexité, en l'occurrence, c'est la surprenante volte-face effectuée par Z._ à la fin de la procédure d'appel, pour tel ou tel motif, alors que les circonstances dûment établies lui donnaient raison. Dans ces conditions, le TAS ne saurait se voir reprocher, sous l'angle de l'art. 190 al. 2 let. e LDIP, d'avoir entériné les sanctions litigieuses sans égard à la Convention.
5. A titre surérogatoire, le recourant soutient que la Formation a violé le principe ne eat iudex ultra petita partium en s'écartant de la Convention pour allouer autre chose que ce qui lui était demandé, à savoir l'annulation intégrale du dispositif de la décision prise par la CRL.
Selon l'art. 190 al. 2 let. c, première hypothèse, LDIP, la sentence peut être attaquée lorsque le tribunal arbitral a statué au-delà des demandes dont il était saisi. Le reproche, basé sur cette disposition, que le recourant adresse au TAS est dénué de tout fondement. En effet, la Formation était saisie de conclusions de la FIFA tendant au rejet des appels et à la confirmation intégrale de la décision attaquée. Par conséquent, en n'admettant que partiellement les appels et en n'annulant que certains chiffres du dispositif de cette décision, elle n'est pas sortie du cadre des demandes qui lui étaient soumises de part et d'autre.
6. Dans un dernier moyen, le recourant se plaint d'une violation de son droit d'être entendu, au sens de l'art. 190 al. 2 let. d LDIP, motif pris de ce que la Formation aurait statué sur son appel sans tenir compte des Faits admis dans la Convention.
Cet ultime moyen ne consiste, toutefois, qu'en la reprise des arguments que le recourant avait développés pour étayer son grief tiré de la violation de l'ordre public procédural. Aussi peut-il être rejeté par simple référence aux considérations émises plus haut relativement à ce grief.
7. Le rejet du recours rend sans objet la demande d'effet suspensif dont celui-ci était assorti.
8. Le recourant, qui succombe, devra payer les frais de la procédure fédérale (art. 66 al. 1 LTF); il versera des dépens à l'intimée (art. 68 al. 1 et 2 LTF), mais pas à Z._ puisque cet autre intimé n'a pas déposé de réponse. L'indemnité allouée à l'intimée sera prélevée sur les sûretés fournies par le recourant.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 6'000 fr., sont mis à la charge du recourant.
3. Le recourant versera à la Fédération Internationale de Football Association (FIFA) une indemnité de 7'000 fr. à titre de dépens; cette indemnité sera prélevée sur les sûretés déposées à la Caisse du Tribunal fédéral.
4. Le présent arrêt est communiqué aux mandataires des parties et au Tribunal Arbitral du Sport (TAS).
Lausanne, le 6 décembre 2012
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Carruzzo