Sachverhalt:
A. A.a Y._ (Kläger, Beschwerdegegner) mit Wohnsitz in A._ ist ein professioneller Fussballtrainer.
Der FC X._ (Beklagter, Beschwerdeführer) ist ein Fussballclub in B._. Er ist Mitglied des nationalen Fussballverbands von B._ und der professionellen Fussballliga des Landes, die beide der Asian Football Confederation (AFC) angehören. Der Nationalverband von B._ ist zudem Mitglied der Fédération Internationale de Football Association (FIFA).
A.b Am 25. März 2009 unterzeichneten die Parteien zusammen mit der W._ GmbH, Zug, ein Memorandum of Understanding über die Hauptpunkte eines noch abzuschliessenden Arbeitsvertrags.
Am 6. Juni 2009 schlossen die Parteien sowie die W._ GmbH eine als "Employment Agreement" bezeichnete Vereinbarung ab, die sowohl auf Englisch als auch auf Portugiesisch verfasst wurde. Danach verpflichtete sich der FC X._ dazu, Y._ als Trainer seiner ersten Mannschaft anzustellen für den Zeitraum vom 1. Juli 2009 bis zum 31. Dezember 2010, es sei denn, das Arbeitsverhältnis werde durch gegenseitige Übereinkunft bis 31. Dezember 2011 verlängert oder vorzeitig gemäss den entsprechenden Vertragsbestimmungen beendet.
Ziffer 11 des Employment Agreement mit der Überschrift "Vergütung" ("Compensation") lautet (in seiner englischen Fassung) wie folgt:
"In consideration of the services to be provided by the Employee, the W._ will pay the Employee the amount of EUROS 7.500.000 (seven millions, five hundred thousand euros): in the following compensation:
a) Euros 2.500.000, Net of Tax in B._, for the period from the 1 July 2009 to 30 December 2009
b) Euros 2.500.000, Net of Tax in B._ for the period from the 1 January 2010 to 30 June 2010, and
c) Euros 2.500.000, Net of Tax in B._ for the period from the 1 July 2010 to 30 December 2010
..."
Ziffer 16 mit dem Titel "The Guarantee" lautet:
"The undersigned Guarantor, jointly and severally, hereby unconditionally guarantees to the Employee, and assigns that all the payments from the Club and all the financial obligations and consequences that should be originated from this agreement to the Club, will be punctually paid and performed. Hereby agreees to be personally bound by, and personally liable for the breach of, each and every provision of the Agreement (including any amendments or modifications of the Agreement)."
Ziffer 19 des Employment Agreement mit der Überschrift "Default Termination" sieht Folgendes vor:
"...
If the Employee does not receive the cleared funds from Payments within thirty (30) days of the payable schedule date, the Contract will be terminated without further notice. If the Contract is terminated due to the Club non payment, then the Employee shall be entitled to receive from the W._, within 5 days of such termination, a sum as proportional time worked.
The Employee reserves the right to exercise any remedies available to him under the terms of this Contract, including the commencement of legal proceedings against the Club and against the Company.
If the Contract is terminated due to the Club non payment, then the Employee shall be entitled to receive from the W._, within 5 days of such default termination, a sum as proportional time worked.
The W._ will be responsible for the costs and expenses (including, but not limited to, attorney's fees, court costs, and fees and expenses) resulting from, consisting of, or arising out of or in connection with the failure by the Club to perform its obligations under the Agreement, or any amendments thereto."
Ziffer 7 ("Arbitration") lautet wie folgt:
"Any dispute arising from or related to the present contract will be submitted exclusively to the Court of Arbitration for Sport in Lausanne, Switzerland, and resolved definitely in accordance with the Code of sports-related arbitration. Notwithstanding the foregoing provisions of this clause 7 and without prejudice thereto, the parties shall use and until the conclusion of the arbitration shall continue to use their best endeavours to attempt to reach a settlement of their dispute by mediation."
Ziffer 25, überschrieben mit "Governing Law", sieht Folgendes vor:
"This agreement shall be governed by and construed in accordance with Swiss law and each of the parties hereto submits to the non-exclusive jurisdiction of the Swiss courts".
A.c An einem nicht genauer bekannten Datum unterzeichneten der Kläger und der Beklagte eine zweite Vereinbarung ("Second Agreement"), abgefasst auf Russisch und Englisch, ebenfalls betreffend die Anstellung des Klägers als Cheftrainer für den Zeitraum vom 1. Juli 2009 bis 31. Dezember 2010, deren Ziffer 7.1 wie folgt lautet:
"All disputes and disagreements which may arise during performance of obligations under the present contract, coordinate the parties by negotiations. The parties are obliged to abstain from the decision of disputes among themselves in courts of the general jurisdiction for this purpose it is necessary to use the appropriate bodies of Professional football league of B._, Football Federation B._, AFC and FIFA."
A.d Am 26. Mai 2010 unterzeichneten die Parteien sowie W._ GmbH eine als "Settlement Agreement" bezeichnete Vereinbarung. Diese enthält die folgende Präambel:
"I. The Employee is employed by the Club by virtue of the 'Employment Agreement' signed on 6th June 2009.
II. 'The Club' is entering into this Agreement and is duly authorized to do so.
III. According to Article 20, paragraph (b) 'Default Termination' of the Employment Agreement, if the Employee does not receive the cleared funds from Payments within thirty (30) days of the payable schedule date, the Employment Agreement will be terminated without further notice.
IV. This article also states that if the Employment Agreement is terminated due to the Club's non payment, then the Employee shall be entitled to receive from the Club, within 5 days of such termination, a sum equal to the Total Compensation that the Employee would have been entitled to from the date of termination on 31 December 2010.
V. According to Art. 12 'Form of payment' of the Employment Agreement, there is an installment of Euros 2.500.000 payable on 01 January 2010 by the Club to the Employee.
VI. At the present date, the previous amount has not been fully paid. The total outstanding amount is Euros 750.000 Net of Tax ('Net of Tax' as defined in clause 23(b) of the Employment Agreement).
VII. As a consequence of the previous provisions and facts described, the employee is entitled to terminate the Employment Agreement and to receive the remaining amount of the Employment Agreement: Euros 3.250.000 Net of Tax. This is composed by Euros 750.000 outstanding from the partial payment of the second installment, and Euros 2.500.000 from the third installment."
Die Vertragsbestimmungen lauten wie folgt:
"1. The Club agrees to pay and will pay the Employee the amount of Euros 1.000.000 Net of Tax, not later than the 30th June 2010.
2. Subject to the payment being duly received, the Employee will warrant that there will not be any further sums owed to him in concept of the compensation stated on Article 11 of the Employment Agreement.
3. In the case that the payment is not received until the agreed date, 30th June, the total amount to be paid by the Club will be the remaining payments of the Employment Agreement, this is Euros 3.250.000. The Employee shall be entitled to receive this amount from the Club, within 5 days after the Termination Date, as defined in point 5.
The Employee reserves the right to exercise any remedies available to him under the terms of this Agreement, including the commencement of legal proceedings against the Club and against the Guarantor.
The Employee reserves the right to exercise any remedies available to him under the terms of this Agreement, including the commencement of legal proceedings against the Club and against the Guarantor.
...
5.1 The Employee's employment with The Club will terminate on 26th May 2010 ('the Termination Date'), and the employment Agreement dated 6th June 2009 will have no further effect thereafter save in respect of those clauses expressed to apply following the Termination Date.
5.2 Following the Club's request, the Employee will perform diligently all his duties as a Manager and First Team Coach of the Club and exercise the powers as are consistent with his employment until 26th May 2010.
5.2 Following the Club's request, the Employee will perform diligently all his duties as a Manager and First Team Coach of the Club and exercise the powers as are consistent with his employment until 26th May 2010.
... 7. The Guarantee. The undersigned Guarantor, jointly and severally, hereby unconditionally guarantee to the Employee, and assigns that all the payments from the Club and all the financial obligations and consequences that should be originated from this agreement to the Club, will be punctually paid and performed. Hereby agrees to be personally bound by, and personally liable for the breach of the Agreement. It is the guarantor's obligation to satisfy the payment upon simple written request from the Employee.
... 7. The Guarantee. The undersigned Guarantor, jointly and severally, hereby unconditionally guarantee to the Employee, and assigns that all the payments from the Club and all the financial obligations and consequences that should be originated from this agreement to the Club, will be punctually paid and performed. Hereby agrees to be personally bound by, and personally liable for the breach of the Agreement. It is the guarantor's obligation to satisfy the payment upon simple written request from the Employee.
... 8. Governing Law and Jurisdiction
This Agreement is to be construed in accordance with Swiss Law and each of the parties hereto submits to the non-exclusive jurisdiction of the Swiss Courts.
..."
Zwischen den Parteien ist unbestritten, dass die im Settlement Agreement vereinbarten Zahlungen an den Kläger ausgeblieben sind.
B. B.a Am 16. August 2010 erhob Y._ beim Tribunal Arbitral du Sport (TAS) Schiedsklage gegen den FC X._ und beantragte, dieser sei zur Zahlung von EUR 750'000.--, zuzüglich Zins zu 5 % seit 1. Januar 2010, sowie EUR 2.5 Mio., zuzüglich Zins zu 5 % seit 26. Mai 2010, zu verurteilen.
Mit Eingabe vom 25. Oktober 2010 bestritt der Beklagte die Zuständigkeit des TAS; sollte sich das Schiedsgericht für zuständig erklären, sei die Klage abzuweisen.
B.b Am 30. März 2011 setzte das TAS dem Kläger Frist an zu einer thematisch streng beschränkten Stellungnahme sowie einer kurzen und abschliessenden Äusserung zum Einwand der fehlenden Zuständigkeit. Die entsprechende Eingabe des Klägers erfolgte am 25. April 2011.
Am 18. Mai 2011 beantragte der Beklagte, es seien infolge Missachtung der vom Schiedsgericht am 30. März 2011 angeordneten thematischen Beschränkung der Stellungnahme mehrere vom Kläger eingereichte Beilagen aus dem Recht zu weisen; zudem sei ihm selbst die Möglichkeit einer weiteren Eingabe zu gewähren.
Mit Verfügung vom 3. Juni 2011 wies das Schiedsgericht das Ersuchen des Beklagten hinsichtlich der beanstandeten Beilagen zurück. Demgegenüber gewährte es ihm die Möglichkeit zur Stellungnahme zu den Beilagen.
Am 15. Juni 2011 setzte das TAS die Hauptverhandlung in Absprache mit den Parteien auf den 31. August 2011 fest; beide stimmten diesem Datum schriftlich zu.
Am 22. und 24. August 2011 beantragte der Rechtsvertreter des Beklagten, es sei auf die Hauptverhandlung zu verzichten, eventualiter sei diese zu verschieben; gleichzeitig teilte er dem TAS mit, dass er den Beklagten ab dem 24. August 2011 nicht mehr vertrete. Der Kläger widersetzte sich einer Verschiebung und sprach sich dafür aus, das Datum der Verhandlung vom 31. August 2011 beizubehalten.
Am 26. August 2011 teilte das TAS den Parteien mit, die Hauptverhandlung werde am 17. Oktober 2011 abgehalten und forderte die Parteien auf, ihre Teilnahme zu bestätigen und dem Schiedsgericht die Namen ihrer Rechtsvertreter, Übersetzer, Zeugen und Gutachter bis zum 16. September 2011 bekannt zu geben. Dieses Schreiben wurde den Parteien per Telefax und DHL zugestellt und wurde vom Beklagten empfangen (d.h. es liegt ein positiver Sendebericht vom 26. August 2011 und eine Bestätigung von DHL hinsichtlich der Zustellung vom 5. September 2011 vor).
Am 20. September 2011 teilte das TAS den Parteien per Telefax mit, dass der Beklagte die Liste der an der Hauptverhandlung vom 17. Oktober 2011 Teilnehmenden noch nicht eingereicht habe und forderte ihn auf, diese Liste bis zum 26. September 2011 nachzureichen. Obwohl das Faxschreiben vom Beklagten empfangen worden war, blieb eine entsprechende Mitteilung aus. Die ihm am 14. Oktober 2011 ebenfalls per Telefax zugestellte Order of Procedure unterzeichnete der Beklagte nicht.
Die Hauptverhandlung wurde am 17. Oktober 2011 ohne Beisein des Beklagten oder eines Rechtsvertreters in Lausanne abgehalten.
B.c Mit Schiedsentscheid vom 19. März 2012 hiess das TAS die Schiedsklage teilweise gut und verurteilte den Beklagten zur Zahlung von EUR 2.5 Mio., zuzüglich Zins zu 5 % seit 1. Juni 2010.
C. Mit Beschwerde in Zivilsachen beantragt der Beklagte dem Bundesgericht, es sei der Schiedsspruch vom 19. März 2012 aufzuheben und die Zuständigkeit des TAS zur Beurteilung der Streitsache zu verneinen. Eventualiter sei der angefochtene Schiedsspruch aufzuheben und die Sache zwecks Ergänzung der Sachverhaltsermittlung an das Schiedsgericht zurückzuweisen.
In prozessualer Hinsicht beantragt der Beschwerdeführer, es sei der Beschwerde aufschiebende Wirkung zu erteilen; zudem seien die schiedsgerichtlichen Akten beizuziehen, es sei ihm Akteneinsicht zu gewähren und Frist zur Ergänzung der Beschwerde anzusetzen.
Der Beschwerdegegner beantragt in seiner Antwort vom 23. Oktober 2012 die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das TAS schliesst in seiner Vernehmlassung auf Abweisung der Beschwerde.
Der Beschwerdeführer wurde mit Präsidialbrief vom 9. August 2012 darauf aufmerksam gemacht, dass es ihm freigestellt sei, eine Beschwerdeergänzung einzureichen, wenn er eine solche für zulässig erachte, dass über deren Zulässigkeit und Berücksichtigung bei der Entscheidfindung jedoch erst im Endurteil entschieden werde, weshalb keine Frist zur Ergänzung der Beschwerde angesetzt werde. Am 17. August 2012 reichte der Beschwerdeführer dem Bundesgericht eine Beschwerdeergänzung ein.
Der Beschwerdeführer reichte dem Bundesgericht am 12. November 2012 eine Replik, der Beschwerdegegner am 30. November 2012 eine Duplik ein.
D. Mit Verfügung vom 30. Juli 2012 erteilte das Bundesgericht der Beschwerde aufschiebende Wirkung und stellte dem Beschwerdeführer die Akten des TAS zur Einsichtnahme zu.

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 bzw. Wohnsitz 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). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 3.3.4 S. 616 mit Hinweisen). Der Antrag des Beschwerdeführers ist insofern zulässig.
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. 3.1 S. 567; <ref-ruling> E. 3b S. 382).
2.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es 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. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141; 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 In der Beschwerde wird hinsichtlich der Notwendigkeit einer Beschwerdeergänzung ausgeführt, der Beschwerdeführer habe die entscheidrelevanten Unterlagen "in der Kürze der Zeit" nicht erhältlich machen können; auch sei er vor der Vorinstanz "nicht rechtsgenüglich vertreten" gewesen. Er verfüge deshalb auch über keine Prozessakten. Die Vorinstanz habe ihm die Akten trotz entsprechenden Gesuchs bisher nicht zugestellt. Mit Eingabe vom 6. August 2012 berief sich der Beschwerdeführer pauschal darauf, es sei ihm die "zur Begründung der Beschwerde ans Bundesgericht notwendige Einsicht in die Vorakten" innerhalb der Beschwerdefrist nicht gewährt worden. Auch in seiner Beschwerdeergänzung vom 17. August 2012 weist der Beschwerdeführer in allgemeiner Weise darauf hin, aufgrund der bisher fehlenden "Einsicht in die entscheidrelevanten Akten" habe sich die Notwendigkeit einer Ergänzung der Beschwerde ergeben.
Eine Nachfristansetzung zur Ergänzung einer nicht genügend begründeten Beschwerde ist in Art. 42 Abs. 5 und 6 BGG nicht vorgesehen (vgl. <ref-ruling> E. 2.4 S. 247). Vielmehr hat die Begründung gemäss <ref-law> in der innerhalb der Rechtsmittelfrist (vgl. <ref-law>) einzureichenden Beschwerdeschrift zu erfolgen. Ergänzende Beschwerdeschriften sind nur unter den engen Voraussetzungen von <ref-law> möglich, die vorliegend nicht erfüllt sind. Der Beschwerdeführer vermag mit seinen Ausführungen auch nicht etwa aufzuzeigen, dass die Möglichkeit einer Beschwerdeergänzung im Beschwerdeverfahren nach Ablauf der Rechtsmittelfrist zur Wahrung des rechtlichen Gehörs erforderlich wäre. Der Beschwerdeführer war bis zum 24. August 2011 im Verfahren vor dem TAS unbestrittenermassen rechtlich vertreten. Der Umstand, dass er ab diesem Zeitpunkt auf eine aktive Verfahrensteilnahme verzichtete, sich bis zum Urteilszeitpunkt passiv verhielt und auf verfahrensleitende Anordnungen des TAS nicht reagierte, kann nicht dazu führen, dass eine gesetzliche und nicht erstreckbare Frist zur Einreichung und Begründung einer Beschwerde in Zivilsachen hinfällig wird. Sein Begehren, nach einer pauschalen Einsicht in die gesamten Vorakten nochmals Gelegenheit zur Ergänzung der Beschwerdeschrift eingeräumt zu erhalten, verdient keinen Rechtsschutz.
Überdies wurden gemäss Eingabe des TAS vom 25. Mai 2012 sowie dem beigelegten Schreiben an den heutigen Rechtsvertreter des Beschwerdeführers (Beilage 9) diesem die Akten für den Zeitraum nach dem 24. August 2011 vom Generalsekretär des TAS am 4. Mai 2012 - und damit noch innerhalb der mit Entscheidzustellung per Post am 25. April 2012 ausgelösten Beschwerdefrist - zugestellt. Der Beschwerdeführer bestätigt in mehreren Eingaben selber, dass ihm der Generalsekretär des TAS am 4. Mai 2012 verschiedene Dokumente in Kopie zugestellt hat. Er verzichtet in seiner Stellungnahme vom 10. Juli 2012 ausdrücklich auf Bemerkungen zum betreffenden Schreiben und zeigt auch in seiner Beschwerdeergänzung vom 17. August 2012 nach gewährter Akteneinsicht durch das Bundesgericht nicht auf, von welchen Dokumenten er erst durch diese Akteneinsicht Kenntnis erlangt hätte und inwiefern diese eine Ergänzung der Beschwerdeschrift erfordern würden. Vielmehr äussert sich der Beschwerdeführer auch in seiner Beschwerdeergänzung unter Hinweis auf den angefochtenen Entscheid sowie seine eigenen Eingaben im Schiedsverfahren zur angeblichen Unzuständigkeit des TAS und rügt eine unzutreffende Auslegung der im Schiedsentscheid aufgeführten Vereinbarungen sowie eine Verletzung des Gehörsanspruchs. Seine Ausführungen lassen nicht im Entferntesten erkennen, inwiefern er dies erst infolge der gewährten Akteneinsicht nach Ablauf der Beschwerdefrist hätte vorbringen können. Seine Ausführungen in der Beschwerdeergänzung vom 17. August 2012 zur Zuständigkeitsfrage haben somit unbeachtet zu bleiben. Entsprechendes gilt für die Gehörsrüge im Zusammenhang mit seinem am 18. Mai 2011 im Rahmen des Schiedsverfahrens gestellten Ersuchen, zur Eingabe des Beschwerdegegners vom 25. April 2011 Stellung nehmen zu können.
Ob seine übrigen Ausführungen in der Beschwerdeergänzung vom 17. August 2012 berücksichtigt werden können, mit denen er eine Ungleichbehandlung der Parteien und eine Verletzung des rechtlichen Gehörs behauptet, braucht nicht vertieft zu werden: Soweit sich seine Vorbringen zum Verfahrensablauf ab dem 24. August 2011 nicht als appellatorisch erweisen, indem er in unzulässiger Weise von den tatsächlichen Sachverhaltsfeststellungen im angefochtenen Entscheid abweicht und dem Bundesgericht seine eigene Sicht der Dinge unterbreitet, wären sie ohnehin haltlos, wie anschliessend zu zeigen ist.
3. Die in der Beschwerdeergänzung vom 17. August 2012 erhobenen Rügen der Ungleichbehandlung der Parteien und der Verletzung des rechtlichen Gehörs sind nicht stichhaltig.
Die Partei, die sich durch eine Verweigerung des rechtlichen Gehörs oder eines anderen nach <ref-law> relevanten Verfahrensmangels 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. Es widerspricht Treu und Glauben, einen Verfahrensmangel erst im Rahmen eines Rechtsmittelverfahrens zu rügen, obwohl im Schiedsverfahren die Möglichkeit bestanden hätte, dem Schiedsgericht die Gelegenheit zur Behebung des angeblichen Mangels zu geben (<ref-ruling> E. 1a S. 388; Urteile 4A_16/2012 vom 2. Mai 2012 E. 3.3; 4A_617/2010 vom 14. Juni 2011 E. 3.1; 4P.72/2001 vom 10. September 2001 E. 4c). Treuwidrig und rechtsmissbräuchlich handelt insbesondere die Partei, die Rügegründe gleichsam in Reserve hält, um diese bei ungünstigen Prozessverlauf und voraussehbarem Prozessverlust nachzuschieben (vgl. <ref-ruling> E. 3.2.2 609; <ref-ruling> E. 3.1 S. 449; <ref-ruling> E. 3c S. 254).
Der Beschwerdeführer war bis zum 24. August 2011 im Verfahren vor dem TAS unbestrittenermassen rechtlich vertreten. Ab diesem Zeitpunkt unterliess er jegliche Teilnahme am Verfahren, reagierte nicht mehr auf verfahrensleitende Anordnungen des Schiedsgerichts und liess sich erst wieder nach Ergehen des Entscheids vom 19. März 2012 vernehmen. Abgesehen davon, dass er sich mit den Ausführungen in der Beschwerdeergänzung in unzulässiger Weise über die - für das Bundesgericht verbindliche (<ref-law>) - Sachverhaltsfeststellung hinwegsetzt, wonach ihm die Verfügung vom 26. August 2011 hinsichtlich der Ansetzung der Hauptverhandlung auf den 17. Oktober 2011 sowohl per Telefax als auch per DHL-Kurier zuging, erfolgt der nunmehr vor Bundesgericht unter Hinweis auf <ref-law> erhobene Vorwurf, er sei seit dem 24. August 2011 nicht mehr am Verfahren beteiligt worden und habe daher auch an der Verhandlung nicht teilnehmen können, treuwidrig. Der - damals noch rechtlich vertretene - Beschwerdeführer hatte mit Schreiben vom 10. bzw. 24. Juni 2011 einer Ansetzung der Verhandlung auf den 31. August 2011 zugestimmt und mit Eingaben vom 22. bzw. 24. August 2011 dem Schiedsgericht noch beantragt, die Verhandlung abzusagen bzw. zu verschieben. Es musste ihm daher bewusst sein, dass eine Verhandlung bevorstand und das Verfahren seinen Lauf nehmen würde. Selbst wenn seine Behauptung zutreffen sollte, dass ihn die nachfolgenden Verfügungen des Schiedsgericht nicht mehr erreicht hätten - wovon nach den Sachverhaltsfeststellungen im angefochtenen Entscheid nicht auszugehen ist -, konnte der Beschwerdeführer nicht einfach untätig bleiben und über ein halbes Jahr zuwarten. Indem er jegliche weitere Beteiligung am Verfahren unterliess und abwartete, ob das Urteil zu seinen Gunsten ausfallen würde, verwirkte er das Recht, sich im bundesgerichtlichen Beschwerdeverfahren auf die geltend gemachten Verfahrensmängel zu berufen.
Dies gilt nicht für die Einrede der Unzuständigkeit des TAS (vgl. <ref-law>), die der Beschwerdeführer im Schiedsverfahren rechtzeitig erhoben hat.
4. Der Beschwerdeführer macht geltend, das TAS habe sich zu Unrecht für zuständig erklärt, da keine gültige Schiedsvereinbarung vorliege (<ref-law>).
4.1 Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt, in rechtlicher Hinsicht frei. Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141).
4.2 Die Gültigkeit einer Schiedsvereinbarung beurteilt sich gemäss <ref-law> in inhaltlicher Hinsicht nach dem von den Parteien gewählten, dem auf die Streitsache, insbesondere dem auf den Hauptvertrag anwendbaren oder dem schweizerischen Recht. Das TAS prüfte das Zustandekommen der Schiedsvereinbarung zutreffend nach schweizerischem Recht. Zu Recht beruft sich auch der Beschwerdegegner nicht auf Bestimmungen einer ausländischen Rechtsordnung, die im konkreten Fall anwendbar und hinsichtlich der materiellen Gültigkeit der Schiedsklausel vorteilhafter als das schweizerische Recht wären.
Unter einer Schiedsvereinbarung ist eine Übereinkunft zu verstehen, mit der sich zwei oder mehrere bestimmte oder bestimmbare Parteien einigen, eine oder mehrere, bestehende oder künftige Streitigkeiten verbindlich unter Ausschluss der ursprünglichen staatlichen Gerichtsbarkeit einem Schiedsgericht nach Massgabe einer unmittelbar oder mittelbar bestimmten rechtlichen Ordnung zu unterstellen (<ref-ruling> E. 3.1 S. 70). Entscheidend ist, dass der Wille der Parteien zum Ausdruck kommt, über bestimmte Streitigkeiten ein Schiedsgericht, d.h. ein nichtstaatliches Gericht, entscheiden zu lassen (<ref-ruling> E. 2.2.3 S. 35; <ref-ruling> E. 2.3 S. 679 f.).
Steht bezüglich der Schiedsvereinbarung kein tatsächlich übereinstimmender Wille der Parteien fest, so ist diese nach dem Vertrauensprinzip auszulegen, d.h. der mutmassliche Wille ist so zu ermitteln, wie er vom jeweiligen Erklärungsempfänger nach Treu und Glauben verstanden werden durfte und musste (<ref-ruling> E. 2.2.3 S. 35 f.; <ref-ruling> E. 3.2 S. 71; <ref-ruling> E. 2.3 S. 680). Bei der Auslegung einer Schiedsvereinbarung ist deren Rechtsnatur zu berücksichtigen; insbesondere ist zu beachten, dass mit dem Verzicht auf ein staatliches Gericht die Rechtsmittelwege stark eingeschränkt werden. Ein solcher Verzichtswille kann nach bundesgerichtlicher Rechtsprechung nicht leichthin angenommen werden, weshalb im Zweifelsfall eine restriktive Auslegung geboten ist (vgl. <ref-ruling> E. 2.3.1 S. 36 f.; <ref-ruling> E. 2.3 S. 680 f.; <ref-ruling> S. 58 E. 2c/aa). Steht demgegenüber als Auslegungsergebnis fest, dass die Parteien die Streitsache von der staatlichen Gerichtsbarkeit ausnehmen und einer Entscheidung durch ein Schiedsgericht unterstellen wollten, bestehen jedoch Differenzen hinsichtlich der Abwicklung des Schiedsverfahrens, greift grundsätzlich der Utilitätsgedanke Platz; danach ist möglichst ein Vertragsverständnis zu suchen, das die Schiedsvereinbarung bestehen lässt (<ref-ruling> E. 2.2.3 S. 36; <ref-ruling> E. 3.2 S. 71 f.; <ref-ruling> E. 2.3 S. 681).
4.3 Entgegen dem, was der Beschwerdegegner anzunehmen scheint, hat das TAS keine tatsächliche Willensübereinstimmung der Parteien festgestellt, bestimmte Streitigkeiten verbindlich unter Ausschluss der ursprünglichen staatlichen Gerichtsbarkeit einem Schiedsgericht zu unterbreiten. Dem angefochtenen Entscheid lassen sich keine Feststellungen einer tatsächlichen Einigung der Parteien hinsichtlich der Streiterledigung entnehmen; das Schiedsgericht hat seiner Auslegung der fraglichen Vereinbarungen daher zutreffend eine objektivierte Betrachtung zugrunde gelegt.
Während das Employment Agreement sowohl eine Schiedsvereinbarung zugunsten des TAS als auch eine Gerichtsstandsklausel enthält, lässt sich dem Settlement Agreement lediglich eine Gerichtsstandsklausel entnehmen. Das nach dem Employment Agreement abgeschlossene Second Agreement sieht eine eigene Regelung hinsichtlich der Streiterledigung vor; es enthält nach zutreffender Ansicht des TAS jedoch keine Schiedsklausel, auf die es seine Zuständigkeit im konkreten Fall stützen könnte. Der Beschwerdegegner bringt denn auch zu Recht nicht vor, die Zuständigkeit des TAS ergebe sich im zu beurteilenden Fall aus dem Second Agreement, sondern erachtet dieses in Übereinstimmung mit dem angefochtenen Schiedsentscheid als nicht massgebend.
4.4 Das Schiedsgericht hat zum Employment Agreement zwar festgehalten, dass dieses neben der Schiedsvereinbarung in Ziffer 7 auch eine Gerichtsstandsklausel (Ziffer 25) zugunsten der (nicht ausschliesslichen) Zuständigkeit der Schweizer Gerichte enthält. Es hat die Schiedsklausel jedoch als gültig erachtet, ohne überhaupt auf das Verhältnis der beiden Klauseln einzugehen. Nachdem der angefochtene Entscheid keine tatsächliche Einigung der Parteien festgestellt hat, die Streitsache von der staatlichen Gerichtsbarkeit auszunehmen und einer schiedsgerichtlichen Entscheidung zu unterstellen, ist die Vereinbarung nach dem Vertrauensprinzip auszulegen.
Die beiden Vertragsbestimmungen sehen je eine unterschiedliche Art der Streiterledigung vor: Während die Schiedsklausel in Ziffer 7 von der ausschliesslichen Zuständigkeit des TAS ausgeht, unterwerfen sich die Parteien nach der Gerichtsstandsklausel von Ziffer 25 der nicht ausschliesslichen Zuständigkeit der Schweizer Gerichte. Weder der Wortlaut des Employment Agreement noch weitere Umstände des Vertragsschlusses lassen konkrete Rückschlüsse hinsichtlich des Verhältnisses der sich widersprechenden Vertragsbestimmungen zu. Der vertraglichen Abmachung fehlt es damit an der Bestimmtheit hinsichtlich der Streitentscheidung durch ein Schiedsgericht; ihr lässt sich nach dem Vertrauensprinzip keine übereinstimmende Willenserklärung entnehmen, Streitsachen aus dem Vertrag von der staatlichen Gerichtsbarkeit auszunehmen und einer Entscheidung durch ein Schiedsgericht zu unterstellen. Insbesondere lässt der Umstand, dass Ziffer 25 die nicht ausschliessliche Zuständigkeit der Schweizer Gerichte vorsieht, nach Treu und Glauben nicht etwa auf den mutmasslichen Willen der Parteien schliessen, dem Kläger wahlweise den Rechtsweg an das TAS oder die staatlichen Gerichte zu eröffnen. Abgesehen davon, dass Ziffer 7 eine ausschliessliche Zuständigkeit des TAS vorsieht ("will be submitted exclusively to the Court of Arbitration for Sport") und damit einem solchen Wahlrecht widerspricht, ist die Wahl eines nicht ausschliesslichen Gerichtsstands ("submits to the non-exclusive jurisdiction") grundsätzlich dahingehend aufzufassen, dass neben dem vertraglich als zuständig erklärten auch andere staatliche Gerichte angerufen werden können. In Ziffer 25 werden daher lediglich die Schweizer Gerichte als zuständig erklärt, ohne einen Zivilprozess vor einem anderen zuständigen staatlichen Gericht auszuschliessen.
Der Beschwerdegegner beruft sich denn auch zu Recht nicht auf ein entsprechendes Wahlrecht, und es kann offenbleiben, unter welchen Voraussetzungen ein solches zulässig wäre (dazu etwa BERNHARD BERGER/FRANZ KELLERHALS, International and Domestic Arbitration in Switzerland, 2. Aufl. 2010, Rz. 460; JEAN-FRANÇOIS POUDRET/SÉBASTIEN BESSON, Comparative law of international arbitration, 2. Aufl. 2007, Rz. 159; vgl. auch JENS-PETER LACHMANN, Handbuch für die Schiedsgerichtspraxis, 3. Aufl., Köln 2008, Rz. 407). Entgegen der in der Beschwerdeantwort vertretenen Ansicht bestehen im Übrigen keine Hinweise darauf, dass die Gerichtsstandsklausel als reine Ersatzzuständigkeit für den Fall zu verstehen wäre, dass die Schiedsklausel keine Wirkung entfalten sollte; es trifft demnach nicht zu, dass die Auslegung des Employment Agreement nach dem Vertrauensprinzip eine eindeutige Rangfolge zwischen den beiden Bestimmungen ergeben würde.
Angesichts der widersprüchlichen vertraglichen Bestimmungen im Employment Agreement kommt darin nach dem Vertrauensprinzip kein hinreichend klarer Wille der Parteien zum Ausdruck, bestimmte Streitigkeiten von der staatlichen Gerichtsbarkeit ausnehmen und darüber ein Schiedsgericht entscheiden zu lassen. Damit bleibt - entgegen der Ansicht des Beschwerdegegners - für den Utilitätsgedanken, nach dem möglichst ein Vertragsverständnis zu suchen ist, das die Schiedsvereinbarung bestehen lässt, kein Raum (<ref-ruling> E. 2.2.3 S. 36; <ref-ruling> E. 3.2 S. 71 f.; je mit Hinweisen).
4.5 Zum gleichen Ergebnis führt eine Gesamtbetrachtung des Employment Agreement vom 6. Juni 2009 und des Settlement Agreement vom 26. Mai 2010, die direkt miteinander in Verbindung stehen, indem dieses eine vergleichsweise Beendigung des gestützt auf das Employment Agreement eingegangenen Arbeitsverhältnisses bezweckt. Das Settlement Agreement sieht lediglich eine (nicht ausschliessliche) Gerichtsstandsklausel vor (Ziffer 8); eine Schiedsklausel ist darin nicht enthalten. Entgegen der Ansicht des TAS kann in Ziffer 5.1 des Settlement Agreement keine Schiedsvereinbarung mittels Verweisung auf Ziffer 7 des Employment Agreement erblickt werden. Abgesehen davon, dass sich die im Employment Agreement enthaltene Schiedsklausel als unwirksam erwiesen hat, verkennt der angefochtene Schiedsentscheid, dass nach der bundesgerichtlichen Rechtsprechung eine zwischen Vertragsparteien in einer aussergerichtlichen Vergleichsvereinbarung enthaltene Gerichtsstandsvereinbarung die in einem früher geschlossenen Vertrag eingefügte Schiedsklausel ersetzt und diese dahinfallen lässt, sofern die Parteien im Vergleich keinen gegenteiligen Willen zum Ausdruck gebracht haben (<ref-ruling> E. 5 S. 496 ff.). Selbst wenn zutreffen sollte, dass gewisse Klauseln des Employment Agreement gestützt auf Art. 5.1 des Settlement Agreement weiter gelten, regelt Letzteres die Höhe der Entschädigung des Beschwerdegegners, die mit der Schiedsklage eingeklagt wird, abschliessend. Entgegen dem, was das TAS anzunehmen scheint, ergibt sich aus Ziffer 5.1 nach Treu und Glauben keine Willensäusserung der Parteien, die Streitsache einem Schiedsgericht zu unterbreiten. Im Gegenteil lässt Ziffer 8 des Settlement Agreement eindeutig darauf schliessen, die staatliche Gerichtsbarkeit beibehalten zu wollen. Unabhängig davon, ob die Vereinbarung der (nicht ausschliesslichen) Zuständigkeit der Schweizer Gerichte gültig oder - wie der Beschwerdegegner vorbringt - infolge mangelnder Bestimmtheit unwirksam ist, lässt sich daraus bei objektiver Betrachtung einzig auf den mutmasslichen Willen der Parteien schliessen, die ordentliche Gerichtsbarkeit der staatlichen Gerichte zu erhalten.
4.6 Damit kommt nach dem Vertrauensprinzip weder im Employment Agreement noch im Settlement Agreement ein hinreichend klarer Wille der Parteien zum Ausdruck, die Streitsache von der staatlichen Gerichtsbarkeit auszunehmen und darüber ein Schiedsgericht entscheiden zu lassen. Vielmehr ist davon auszugehen, dass die Parteien nicht auf die staatliche Gerichtsbarkeit verzichten, sondern den ordentlichen Rechtsweg im Gegenteil offen halten wollten. Entgegen dem angefochtenen Schiedsentscheid liegt keine gültige Schiedsvereinbarung vor und das vom Beschwerdegegner angerufene TAS hat sich für die Beurteilung der Streitsache zu Unrecht für zuständig erklärt.
5. Der angefochtene Schiedsentscheid ist in Gutheissung der Beschwerde aufzuheben und es ist antragsgemäss festzustellen, dass das TAS für die zu beurteilende Streitsache nicht zuständig ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdegegner kosten- und entschädigungspflichtig (<ref-law> und <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der angefochtene Schiedsentscheid des Tribunal Arbitral du Sport vom 19. März 2012 wird aufgehoben.
2. Es wird festgestellt, dass das Tribunal Arbitral du Sport für die zu beurteilende Streitsache nicht zuständig ist.
3. Die Gerichtskosten von Fr. 20'000.-- werden dem Beschwerdegegner auferlegt.
4. Der Beschwerdegegner hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 22'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 17. Januar 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann