Faits: A. X._, né en 1979, est un athlète ... de haut niveau ayant effectué une carrière internationale couronnée de succès. Le 11 août 2011, dans des circonstances qui constituent le noeud du litige, l'athlète se serait soustrait à un contrôle antidopage hors compétition organisé par l'Association internationale des fédérations d'athlétisme (ci-après: l'IAAF, selon son acronyme anglais). Dénoncé pour violation des règles antidopage, X._ a été blanchi, le 6 juin 2012, par la Fédération ... d'athlétisme. B. Le 6 juillet 2012, l'IAAF a déposé un appel auprès du Tribunal Arbitral du Sport (TAS) contre la décision du 6 juin 2012. Avec l'accord des parties, le TAS a eu recours à une procédure accélérée afin qu'une décision puisse être rendue avant le début des Jeux olympiques d'été organisés à Londres du 27 juillet au 12 août 2012, X._ ayant rempli les critères de qualification pour y participer. Une Formation de trois arbitres a été rapidement constituée et les parties ont été conviées à une audience qui s'est déroulée le 24 juillet 2012. Donnant suite à une demande de l'IAAF, le conseil de l'athlète ... a produit, la veille de l'audience, une liasse de documents incluant des relevés téléphoniques concernant son client. Le lendemain de l'audience, soit le 25 juillet 2012, le TAS a communiqué aux parties le dispositif de sa sentence, ainsi formulé: "1. The appeal filed by the IAAF against the decision of 6 June 2012 rendered by the Doping Committee of the ... National Anti-Doping Organisation is upheld. 2. The decision of 6 June 2012 rendered by the Doping Committee of the ... National Anti-Doping Organisation is set aside. 3. Mr X._ is sanctioned with a ban of two years starting from the date of the present award. 4. The issues of the costs of the arbitration and the parties' legal expenses incurred in connection with the arbitration procedure shall be decided in a separate award on costs. 5. All further claims are dismissed." La sentence motivée a été notifiée aux parties le 18 octobre 2012. Son dispositif énonce ce qui suit: "1. The appeal filed by the IAAF against the decision of 6 June 2012 rendered by the Doping Committee of the ... National Anti-Doping Organisation is upheld. 2. The decision of 6 June 2012 rendered by the Doping Committee of the ... National Anti-Doping Organisation is set aside. 3. Mr X._ is sanctioned with a ban of two years starting from the date of the present award, with credit given for any period of suspension previously served. 4. The costs of the arbitration to be calculated and communicated separately to the parties by the CAS Court Office shall be borne in the following proportion: one quarter by the IAAF and three-quarters jointly and severally by the Respondents. 5. Z._ shall make a contribution of CHF 2,000 (...) and Mr X._ shall make a contribution of CHF 1,000 (...) towards the IAAF's legal fees and other expenses incurred in connection with the present arbitration. 6. All further claims are dismissed." Les motifs qui étayent cette sentence seront indiqués, dans la mesure utile, lors de l'examen des griefs formulés à l'encontre de celle-ci. C. Le 13 décembre 2012, X._ (ci-après: le recourant) a formé un recours en matière civile, assorti d'une demande d'assistance judiciaire, en vue d'obtenir l'annulation de la sentence du TAS. Par ordonnance présidentielle du 16 janvier 2013, le recourant a été mis au bénéfice de l'assistance judiciaire gratuite et son conseil désigné comme avocat d'office. Dans sa réponse du 1er mars 2013, le TAS, qui a produit son dossier, a conclu au rejet du recours. L'IAAF (ci-après: l'intimée) en a fait de même au terme de ses observations du 8 mars 2013. Quant à la Fédération ... d'athlétisme, elle n'a pas déposé de réponse dans le délai qui lui avait été imparti pour ce faire. Le recourant a produit une réplique en date du 22 mars 2013. L'intimée et le TAS n'ont pas fait usage de la possibilité de dupliquer qui leur avait été offerte. 