Sachverhalt:
A. A.a Der Club X._ (Beschwerdeführer) ist ein Fussballclub mit Sitz in A._ (Italien). Er ist Mitglied des italienischen Fussballverbandes, der seit 1905 der Fédération Internationale de Football Association (FIFA), einem Verein schweizerischen Rechts (<ref-law>) mit Sitz in Zürich, angehört.
Der Club Y._ (Beschwerdegegner) ist ein Fussballclub mit Sitz in B._ (Honduras). Er ist Mitglied des honduranischen Fussballverbandes, der seit 1946 der FIFA angehört.
A.b Im Mai 1999 gelangten die Parteien via den Spielervermittler C._ in Kontakt. Dabei ging es um den Transfer des honduranischen Fussballspielers D._ vom Beschwerdegegner zum Beschwerdeführer.
Am 1. Juni 1999 fanden diverse Treffen zwischen C._, dem Fussballspieler und dessen Agenten E._, dem sportlichen Direktor des Beschwerdegegners F._ und dem Präsidenten des Beschwerdeführers G._ statt.
Anlässlich der dabei geführten Verhandlungen kam ein vom 1. Juni 1999 datierendes Agreement mit folgendem Wortlaut zustande:
"AGREEMENT
Between
X._,
And
Club Y._
Regarding the transfer of the player Mr. D._ by mean of this document.
1) X._ will pay to the club Y._ the total sum of 2,200,000 USD (...).
[...]
(c) Club Y._ will immediately send the transfer of the player as soon it will receive the total sum guarantee in the form of a stand-by-letter of credit in the name of Club Y._ to be confirmed by Banco H._ that will be issued the 30th July 1999 by Banco I._ on behalf of X._
(2) In case of a future transfer of the player from X._ to a third club, and in case that the revenue will be superior of the sum paid to the Club Y._ as a transfeer fee (...), X._ will pay to the Club Y._ the following royalties calculated on the difference between the sum of point A)a) and the sum received by the other club:
a) 20 % (twenty percent) if the transfer will be less of 7,000,000 USD (seven millions US Dollars);
b) 15 % (fifteen percent) if the transfer will be major of 7,000,000 USD (seven millions US Dollars)."
Die Vertragsurkunde trägt die Unterschriften von G._ für den Beschwerdeführer und von K._ für den Beschwerdegegner.
A.c Am 26. Juni 2007 schlossen der Beschwerdeführer und der italienische Fussballclub L._ einen Vertrag über den Transfer von D._ für eine Transfersumme von 14 Mio. Euro ab.
In der Folge machte der Beschwerdegegner gegenüber dem Beschwerdeführer gestützt auf das Agreement vom 1. Juni 1999 eine Zahlung von mindestens USD 2'514'723.-- aufgrund des Transfers von D._ an den L._ geltend.
Dem hielt der Beschwerdeführer entgegen, dass die Vertragsurkunde, auf der das Agreement vom 1. Juni 1999 festgehalten ist, gefälscht und das Agreement somit ungültig sei.
B. B.a Mit Klage vom 1. November 2007 beantragte der Beschwerdegegner der FIFA, es sei der Beschwerdeführer zur Zahlung eines Betrages von mindestens USD 2'514'723.-- zu verurteilen.
Mit Entscheid vom 22. März 2010 hiess der Einzelrichter der FIFA Kommission für den Status von Spielern die Klage gut und verurteilte den Beschwerdeführer zur Zahlung von USD 2'514'723.-- an den Beschwerdegegner.
B.b Dagegen erhob der Beschwerdeführer am 9. August 2011 Berufung beim Tribunal Arbitral du Sport (TAS) in Lausanne. Er beantragte, es sei der Entscheid des Einzelrichters der FIFA Kommission für den Status von Spielern aufzuheben und die Klage des Beschwerdegegners abzuweisen.
Mit Schiedsentscheid vom 15. September 2011 (CAS 2010/A/2193) wies das TAS die Berufung ab und bestätigte den Entscheid des Einzelrichters der FIFA Kommission für den Status von Spielern.
Das TAS kam zum Schluss, dass das Agreement vom 1. Juni 1999 echt und damit gültig sei.
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsentscheid vom 15. September 2011 (CAS 2010/A/2193) aufzuheben und es sei die Streitsache zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
Der Beschwerdegegner beantragt in seiner Vernehmlassung die Abweisung der Beschwerde. Die Vorinstanz hat auf Vernehmlassung verzichtet. Die Parteien reichten Replik und Duplik ein.
Die Akten des Schiedsverfahrens wurden beigezogen.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache redigiert, verwendet das Bundesgericht die von den Parteien gewählte Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht der deutschen Sprache bedienen, ergeht der Entscheid des Bundesgerichts auf Deutsch.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Beide Parteien hatten im relevanten Zeitpunkt ihren Sitz ausserhalb der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden).
Der Beschwerdeantrag erweist sich somit insoweit als zulässig, als die Aufhebung des angefochtenen Entscheids verlangt wird. Soweit hingegen die Rückweisung der Streitsache an die Vorinstanz zur neuen Entscheidung verlangt wird, ist auf die Beschwerde nicht einzutreten.
2.3 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
2.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des Schiedsverfahrens, namentlich die Parteivorbringen (Urteile 4A_210/2009 vom 7. April 2010 E. 2; 4A_439/2010 vom 20. Oktober 2011 E. 2.1). Das Bundesgericht kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
2.5 Der Beschwerdeführer verkennt diese Grundsätze teilweise: Er stellt seinen rechtlichen Vorbringen eine mehrseitige Sachverhaltsdarstellung voran, in der er die Hintergründe der Auseinandersetzung sowie des Verfahrens aus eigener Sicht schildert. Dabei weicht er über weite Strecken von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitert diese, ohne substanziiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. Diese Darlegungen haben insoweit unbeachtet zu bleiben. Soweit sich der Beschwerdeführer sodann unter dem Titel "C. Angeblich fehlende Scheinvollmacht von C._" direkt gegen die vorinstanzlichen Sachverhaltsfeststellungen richtet, verkennt er die Anforderungen an die Begründung einer Sachverhaltsrüge. Es genügt nicht, in diesem Zusammenhang lediglich das Vorliegen des Rügegrundes von <ref-law> bzw. die Verletzung des Anspruchs auf Durchführung eines kontradiktorischen Verfahrens zu behaupten, ohne diesen Vorwurf auch nur im Ansatz in nachvollziehbarer Weise zu erläutern. Darauf ist nicht einzutreten.
3. Der Beschwerdeführer rügt, die Vorinstanz habe sein rechtliches Gehör verletzt (<ref-law>), indem sie seinem Antrag, es sei das Agreement vom 1. Juni 1999 von einem Experten auf Echtheit zu überprüfen, nur teilweise entsprochen habe. Die Vorinstanz habe dem unabhängigen Experten Dr. N._ lediglich den Auftrag gegeben, die Echtheit der Unterschriften zu überprüfen, anstatt wie beantragt eine Überprüfung des gesamten Dokumentes anzuordnen. Dieser Mangel sei auch durch den zweiten Expertenbericht vom 20. April 2012 nicht behoben worden, da der Beschwerdeführer keine Möglichkeit gehabt habe, den Experten hierzu mündlich "eingehend zu verhören". Eine weitere Gehörsverletzung sieht der Beschwerdeführer zudem darin, dass die Vorinstanz seinen Antrag, es sei das Agreement von einem von ihm benannten (Partei-)Experten auf Echtheit zu überprüfen, abgewiesen hat.
3.1 Die Partei, die sich durch eine Verweigerung des rechtlichen Gehörs oder einen anderen nach <ref-law> relevanten Verfahrensmangel für benachteiligt hält, verwirkt ihre Rügen, wenn sie diese nicht rechtzeitig im Schiedsverfahren vorbringt und nicht alle zumutbaren Anstrengungen unternimmt, um den Mangel zu beseitigen (Urteil 4A_617/2010 vom 14. Juni 2011 E. 3.1, publ. in: ASA Bulletin 1/2012, S. 138 ff., 141 f.; <ref-ruling> E. 1a S. 388; in Bezug auf Ablehnungsgründe: <ref-ruling> E. 3c S. 253 f.; vgl. nunmehr auch den revidierten Art. 1466 des französischen Code de procédure civile: "La partie qui, en connaissance de cause et sans motif légitime, s'abstient d'invoquer en temps utile une irrégularité devant le tribunal arbitral est réputée avoir renoncé à s'en prévaloir"; gemäss dem Rapport au Premier ministre relatif au décret n° 2011-48 du 13 janvier 2011 portant réforme de l'arbitrage, in: Journal officiel de la République française, Texte 8, soll damit das angelsächsische "principe de l'estoppel" kodifiziert werden). Denn es widerspricht Treu und Glauben, einen Verfahrensmangel erst im Rahmen eines Rechtsmittelverfahrens zu rügen, obgleich im Schiedsverfahren die Möglichkeit bestanden hätte, dem Schiedsgericht die Gelegenheit zur Behebung dieses Mangels zu geben (<ref-ruling> E. 1a S. 388; Urteil 4P.72/2001 vom 10. September 2001 E. 4c). Treuwidrig und rechtsmissbräuchlich handelt insbesondere die Partei, welche Rügegründe gleichsam in Reserve hält, um diese bei ungünstigem Prozessverlauf und voraussehbarem Prozessverlust nachzuschieben (vgl. <ref-ruling> E. 3c S. 254).
3.1 Die Partei, die sich durch eine Verweigerung des rechtlichen Gehörs oder einen anderen nach <ref-law> relevanten Verfahrensmangel für benachteiligt hält, verwirkt ihre Rügen, wenn sie diese nicht rechtzeitig im Schiedsverfahren vorbringt und nicht alle zumutbaren Anstrengungen unternimmt, um den Mangel zu beseitigen (Urteil 4A_617/2010 vom 14. Juni 2011 E. 3.1, publ. in: ASA Bulletin 1/2012, S. 138 ff., 141 f.; <ref-ruling> E. 1a S. 388; in Bezug auf Ablehnungsgründe: <ref-ruling> E. 3c S. 253 f.; vgl. nunmehr auch den revidierten Art. 1466 des französischen Code de procédure civile: "La partie qui, en connaissance de cause et sans motif légitime, s'abstient d'invoquer en temps utile une irrégularité devant le tribunal arbitral est réputée avoir renoncé à s'en prévaloir"; gemäss dem Rapport au Premier ministre relatif au décret n° 2011-48 du 13 janvier 2011 portant réforme de l'arbitrage, in: Journal officiel de la République française, Texte 8, soll damit das angelsächsische "principe de l'estoppel" kodifiziert werden). Denn es widerspricht Treu und Glauben, einen Verfahrensmangel erst im Rahmen eines Rechtsmittelverfahrens zu rügen, obgleich im Schiedsverfahren die Möglichkeit bestanden hätte, dem Schiedsgericht die Gelegenheit zur Behebung dieses Mangels zu geben (<ref-ruling> E. 1a S. 388; Urteil 4P.72/2001 vom 10. September 2001 E. 4c). Treuwidrig und rechtsmissbräuchlich handelt insbesondere die Partei, welche Rügegründe gleichsam in Reserve hält, um diese bei ungünstigem Prozessverlauf und voraussehbarem Prozessverlust nachzuschieben (vgl. <ref-ruling> E. 3c S. 254).
3.2 3.2.1 In seiner Berufung vom 9. August 2010 stellte der Beschwerdeführer den Antrag, es sei das Original des Agreements vom 1. Juni 1999 von einem vom TAS zu ernennenden, unabhängigen Experten auf seine Echtheit hin überprüfen zu lassen. Falls dieser Experte zum Schluss kommen sollte, das Dokument sei echt, sei dem Beschwerdeführer zudem das Recht zu gewähren, einen eigenen Experten zu bezeichnen.
Mit Schreiben vom 26. Oktober 2010 teilte das TAS den Parteien mit, dass es einen unabhängigen Experten damit beauftragen werde, das Dokument auf seine Echtheit hin zu überprüfen. Den Antrag des Beschwerdeführers, es sei ihm das Recht zu gewähren, einen eigenen Experten zu benennen, falls der unabhängige Experte auf Echtheit schlösse, wies das TAS ab.
Am 22. Dezember 2010 beauftragte das TAS Dr. N._ vom O._ der Universität Lausanne als unabhängigen Experten mit der Abklärung der Frage, ob die Unterschrift von G._ auf dem Agreement vom 1. Juni 1999 echt sei.
Im Expertenbericht vom 12. Januar 2011 kam Dr. N._ zum Schluss, dass die Unterschrift von G._ echt sei.
Mit Eingabe vom 24. Januar 2011 nahm der Beschwerdeführer Stellung zum Expertenbericht und kritisierte, dass dieser sich einzig zur Frage äussere, ob die Unterschrift auf dem Agreement echt sei, während der Beschwerdeführer beantragt habe, die Echtheit des Agreements als Ganzes zu untersuchen. Aus diesem Grund stellte sich der Beschwerdeführer gegen "jegliche Berücksichtigung" des Expertenberichts "im vorliegenden Schiedsverfahren" ("to any sort of the Opinion's consideration in the present arbitrational proceedings").
Anlässlich der Schiedsverhandlung vom 1. Februar 2011 wurde der Experte Dr. N._ angehört. Aufgrund der Einwände des Beschwerdeführers zum ersten Expertenbericht beauftragte das Schiedsgericht den Experten mit weiteren Abklärungen zur Echtheit des Agreements vom 1. Juni 1999.
Im zweiten Expertenbericht vom 20. April 2011 kam Dr. N._ zum Schluss, dass auch der Briefkopf des untersuchten Dokuments echt sei und keine Anhaltspunkte bestünden, welche die Echtheit des Dokuments in Frage stellen würden.
Hierzu nahm der Beschwerdeführer mit Eingabe vom 4. Mai 2011 Stellung. Er beschränkte sich dabei auf die Behauptung, dass der Beschwerdegegner sowohl in sachverhaltlicher wie rechtlicher Hinsicht keinen Anspruch gegenüber dem Beschwerdeführer habe und dass dies völlig unabhängig von der Echtheit des Agreements vom 1. Juni 1999 sei ("such outcome being entirely independent of the authenticity/non-authenticity of the 'Agreement' dated 1 June 1999"). Die angebliche Echtheit des vom Experten untersuchten Agreements sei deshalb ohne Belang ("would therefore not be important").
3.2.2 In der Stellungnahme vom 4. Mai 2011 hat der Beschwerdeführer weder beantragt, es sei Dr. N._ zum zweiten Expertenbericht anzuhören, noch hat er den Antrag auf Ernennung eines Parteiexperten aufrecht erhalten. Ebenso wenig hat er eine Verletzung des rechtlichen Gehörs gerügt. Im Gegenteil hat er es als belanglos bezeichnet, ob das Agreement vom 1. Juni 1999 echt sei. Damit durfte und musste die Vorinstanz davon ausgehen, dass der Beschwerdeführer in Bezug auf die Abklärungen zur Echtheit des Dokuments keine formellen Einwände mehr hat.
Hätte der Beschwerdeführer dennoch dafür gehalten, dass sein rechtliches Gehör verletzt worden sei, hätte er eine entsprechende Rüge vor Ausfällung des angefochtenen Entscheids vom 15. September 2011 ohne Weiteres vortragen und dadurch dem Schiedsgericht die Gelegenheit zur Behebung des angeblichen Mangels geben können. Indem er dies unterliess und abwartete, ob das Urteil zu seinen Gunsten ausfallen würde, verwirkte er das Recht, sich im Rechtsmittelverfahren vor Bundesgericht auf eine Verletzung des rechtlichen Gehörs zu berufen. Auf die entsprechende Rüge ist nicht einzutreten.
4. Der Beschwerdeführer macht sodann geltend, die Vorinstanz habe sein rechtliches Gehör (<ref-law>) verletzt sowie gegen den verfahrensrechtlichen Ordre public (<ref-law>) verstossen, indem sie die schriftliche Zeugenaussage von C._ nicht berücksichtigt habe.
4.1 <ref-law> lässt die Anfechtung allein wegen der zwingenden Verfahrensregeln gemäss <ref-law> zu. Danach muss das Schiedsgericht insbesondere den Anspruch der Parteien auf rechtliches Gehör wahren. Dieser entspricht - mit Ausnahme des Anspruchs auf Begründung - dem in <ref-law> gewährleisteten Verfassungsrecht (<ref-ruling> E. 5 S. 37 f.; <ref-ruling> E. 4b S. 243; <ref-ruling> E. 2c S. 578 f.). Die Rechtsprechung leitet daraus insbesondere das Recht der Parteien ab, sich über alle für das Urteil wesentlichen Tatsachen zu äussern, ihren Rechtsstandpunkt zu vertreten, ihre entscheidwesentlichen Sachvorbringen mit tauglichen sowie rechtzeitig und formrichtig offerierten Mitteln zu beweisen, sich an den Verhandlungen zu beteiligen und in die Akten Einsicht zu nehmen (<ref-ruling> E. 5 S. 38; <ref-ruling> E. 2c S. 578 f.; je mit Hinweisen).
Auch im schiedsgerichtlichen Verfahren gilt der Gehörsanspruch indessen nicht unbegrenzt. So ist es dem Schiedsgericht nicht verboten, den Sachverhalt nur aufgrund der als tauglich und erheblich erachteten Beweismittel festzustellen (<ref-ruling> E. 1b S. 389; <ref-ruling> E. 4c S. 644). Das Schiedsgericht kann daher auf eine Beweisabnahme verzichten, wenn der entsprechende Beweisantrag eine nicht rechtserhebliche Tatsache betrifft, wenn das angebotene Beweismittel offensichtlich untauglich ist oder wenn das Gericht aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (vgl. dazu <ref-ruling> E. 5.3; <ref-ruling> E. 2.1 S. 429; <ref-ruling> E. 4a). Die antizipierte Würdigung von Beweisen durch ein internationales Schiedsgericht kann im Beschwerdeverfahren nur unter dem beschränkten Blickwinkel einer Verletzung des Ordre public überprüft werden (Urteile 4A_600/2010 vom 17. März 2011 E. 4.1; 4P.23/2006 vom 27. März 2006 E. 3.1; 4P.114/2003 vom 14. Juli 2003 E. 2.2).
4.2 Die Vorinstanz hat sich in Erwägung 2.8 ihres Entscheids mit der schriftlichen Zeugenaussage von C._ auseinandergesetzt. Sie hat ausgeführt, dass gemäss dieser Zeugenaussage am 1. Juni 1999 ein Treffen zwischen G._ und K._ im Büro des Vorsitzenden des Beschwerdeführers in A._ stattgefunden habe. Die Anwesenheit von K._ am 1. Juni 1999 in A._ werde indessen durch andere Beweismitteln in Frage gestellt, namentlich durch die Zeugenaussagen von K._ selbst sowie von F._ und E._. Nach reiflicher Überlegung komme die Vorinstanz zum Schluss, dass K._ am 1. Juni 1999 nicht physisch in A._ anwesend gewesen sei. In diesem Zusammenhang stütze sich die Vorinstanz auf die Zeugenaussage von E._, der anlässlich der Schiedsverhandlung vom 1. Februar 2011 mündlich bestätigt habe, dass K._ während des Vertragsabschlusses nicht anwesend gewesen sei.
Diesen Erwägungen fügte die Vorinstanz wörtlich Folgendes hinzu:
"The Panel is also of the opinion that the witness statement of C._ is not to be taken into account, if not confirmed by other evidence, because C._ decided at the last moment not to appear at the hearing held in front of the Panel, and by this surprising even the Appellant and its Counsel. Moreover, the Panel found that there were contradictions between the written witness statement of C._, and the testimony of the president of the Appellant, who testified orally at the hearing."
Daraus folgt, dass die Vorinstanz die schriftliche Zeugenaussage von C._ keineswegs ignoriert oder unbeachtet gelassen, sondern durchaus abgenommen, analysiert, den anderen Beweismitteln gegenüber gestellt und auf Übereinstimmung hin überprüft hat (vgl. den Hinweis auf "contradictions between the written witness statement of C._, and the testimony of the president of the Appellant"). Darin, dass die Vorinstanz der schriftlichen Zeugenaussage von C._ keine Bedeutung zumessen will, soweit sie nicht durch andere Beweismittel bestätigt wird, liegt somit Beweiswürdigung. Von einer Nichtberücksichtigung der Zeugenaussage von C._ kann keine Rede sein. Eine Verletzung des rechtlichen Gehörs liegt nicht vor.
4.3 Soweit der Beschwerdeführer im Zusammenhang mit der schriftlichen Zeugenaussage von C._ auch den formellen Ordre public anruft, kann darauf nicht eingetreten werden, gehen doch die speziellen Anfechtungsgründe von Art. 190 Abs. 2 lit. a-d IPRG demjenigen nach <ref-law> vor (Urteile 4A_600/2010 vom 17. März 2011 E. 4.3 in: ASA Bulletin 2012, S. 119 ff., 125; 4P.105/2006 vom 4. August 2006 E. 5.3 in: ASA Bulletin 2007, S. 105 ff., 114).
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 i.V.m. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 20'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 22'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 31. Mai 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni