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. 