Sachverhalt: A. A.a M._ (Kläger, Beschwerdegegner) ist ein professioneller Fussballtrainer. Nach Beendigung seiner aktiven Fussballkarriere begann er im Jahr 1988 seine Trainerlaufbahn und war lange in Spanien tätig, unter anderem als Trainer von Real Saragossa, Real Madrid, Atlético Madrid und FC Barcelona. M._ hat seinen gesetzlichen Wohnsitz seit beinahe 30 Jahren in Spanien und hat - zusätzlich zu seiner serbischen Nationalität - die spanische Staatsbürgerschaft angenommen. Der Serbische Fussballverband (Beschwerdeführer, Beklagter) mit Sitz in Belgrad ist der Nationalverband für den Fussballsport der Republik Serbien und als solcher Mitglied der Fédération Internationale de Football Association (FIFA) sowie der Union des Associations Européennes de Football (UEFA). A.b Am 25. August 2008 schloss M._ mit dem Serbischen Fussballverband einen Arbeitsvertrag ab, mit dem er während der Qualifikationsrunde (1. September 2008 - 30. November 2009) für die FIFA-Weltmeisterschaft 2010 als Cheftrainer der serbischen Nationalmannschaft angestellt wurde. Nachdem sich das Nationalteam in der Folge für die Weltmeisterschaft in Südafrika qualifiziert hatte, verhandelten die Parteien im Dezember 2009 über eine Weiterführung der Zusammenarbeit. Am 16. Dezember 2009 unterzeichneten sie einen neuen Arbeitsvertrag für den Zeitraum vom 1. Januar 2010 bis 30. Juni 2012, der die Vereinbarung vom 25. August 2008 ersetzte. Der neue Vertrag sah für die Zeitperiode von Januar 2010 bis Oktober 2011 eine monatliche Entschädigung von EUR 70'000.-- und für die restliche Vertragsdauer ein monatliches Gehalt von EUR 100'000.-- vor, zahlbar in der serbischen Landeswährung Dinar (RSD), berechnet nach dem Verkaufskurs der serbischen Nationalbank am Zahlungstag. Vereinbart war zusätzlich ein Bonus in Form einer Marketinggebühr ("marketing fee"), welche die bisherigen Bemühungen des Klägers im Hinblick auf die erfolgreiche Positionierung des Serbischen Fussballverbands sowie dessen Einkünfte infolge der Qualifikation für die FIFA-Weltmeisterschaft 2010 abgelten sollte. Die Marketinggebühr war auf EUR 660'000.-- festgesetzt, zahlbar in zwei Raten, jeweils per Ende 2009 und 2010. In Bezug auf die Streiterledigung sieht Ziffer 13 des Arbeitsvertrags vom 16. Dezember 2009 Folgendes vor: "In case of a dispute arising out of this contract, the competent bodies of the FAS, UEFA and CAS (Court of Arbitration for Sports) in Lausanne, Switzerland shall have jurisdiction thereof. The parties hereto agree that the party initiating the procedure shall be entitled to choose the competent body before which the procedure will be instituted". A.c Aufgrund einer Beschimpfung des Schiedsrichters anlässlich eines Spiels gegen Australien im Rahmen der Weltmeisterschaft wurde der Kläger am 3. Juli 2010 von der FIFA-Disziplinarkommission für vier Spiele mit einer Sperre (sog. "touchline bar") belegt und mit einer Busse von Fr. 14'000.-- bestraft. Die Beschwerdekommission der FIFA bestätigte diesen Entscheid am 29. Juli 2010. Am 15. August 2010 bezahlte der Beklagte die dem Kläger auferlegte Busse. Die Parteien verhandelten in der Folge erfolglos über eine Abänderung der vertraglich vereinbarten Entschädigung. Unter anderem unterbreitete der Beklagte dem Kläger am 10. September 2010 einen Zusatz zum Arbeitsvertrag mit einer neuen Entschädigungsregelung, zusammen mit der Aufforderung zur Unterzeichnung innert fünf Tagen nach Empfang des Dokuments. Am 15. September 2010 liessen die Rechtsvertreter des Klägers dem Beklagten per E-Mail ihre Bemerkungen zum vorgeschlagenen Vertragszusatz zukommen. Noch am gleichen Tag kündigte der Beklagte den Arbeitsvertrag mit dem Kläger per sofort, unter anderem wegen angeblicher grober Verletzung vertraglicher Pflichten. B. B.a Am 20. September 2010 reichte M._ beim Tribunal Arbitral du Sport (TAS) Schiedsklage ein, im Wesentlichen mit dem (im Laufe des Verfahrens geänderten) Antrag, es sei der Serbische Fussballverband zur Zahlung von netto EUR 2'150'000.-- zu verurteilen, zu überweisen in Dinar nach dem Durchschnittskurs der serbischen Nationalbank, und zur Zahlung einer Entschädigung im Gegenwert von EUR 280'000.-- nach Art. 337c Abs. 3 des schweizerischen Obligationenrechts, jeweils zuzüglich Zins zu 5 %: "1. to order the Respondent to pay to the Claimant a net amount of EUR 2,150,000 in Dinar counter value at the average rate of the National Bank of Serbia on the following due dates: a. EUR 70,000 in Dinar counter value of 11 August 2010; b. EUR 70,000 in Dinar counter value of 11 September 2010; c. EUR 300,000 in Dinar counter value of 15 September 2010; d EUR 1,710,000 in Dinar counter value of 15 September 2010. 2. to order Respondent to pay interest at the Swiss statutory rate of 5 per cent per annum as follows: a. as of 11 August 2010, on the amount of EUR 70,000 in Dinar counter value; b. as of 11 September 2010, on the amount of EUR 70'000 in Dinar counter value; c. as of 15 September 2010, on the amount of EUR 300,000 in Dinar counter value; d. as of 15 September 2010, on the amount of EUR 1,710,000 in Dinar counter value. 3. to order Respondent to pay to Claimant an indemnity of EUR 280,000 in Dinar counter value at the average rate of the National Bank of Serbia on the date of CAS' decision (Article 337c para. 3 of the Code of Obligations); ..." B.b Mit Schiedsentscheid vom 23. September 2011 erachtete das TAS die Kündigung des Arbeitsverhältnisses durch den Beklagten als unrechtmässig und hiess die Klage weitgehend gut: "1. The relief requested by M._ against the Football Association of Serbia is partially upheld. 2. The Football Association of Serbia is ordered to pay to M._, net of any taxes, the following amounts in RDS counter value at the selling exchange rate of the National Bank of Serbia prevailing on the dates indicated herein below: a. EUR 70,000 plus 5% interest p.a. as of 11 August 2010 until the date of effective payment; b. EUR 70,000 plus 5% interest p.a. as of 11 September 2010 until the date of effective payment; c. EUR 1,710,000 plus 5% interest p.a. as of 15 September 2010 until the date of effective payment. d. EUR 140,000 plus 5% interest p.a. as of 15 September 2010 until the date of effective payment. 3. The Football Association of Serbia is ordered to pay to M._, net of any taxes, EUR 300,000 plus 5% interest p.a. as of 15 September 2010 until the date of effective payment. ..." C. Mit Beschwerde in Zivilsachen beantragt der Beklagte dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 23. September 2011 aufzuheben. Der Beschwerdegegner beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das TAS beantragt die Abweisung der Beschwerde. Der Beschwerdeführer reichte dem Bundesgericht am 17. Februar 2012 eine Replik, der Beschwerdegegner am 7. März 2012 eine Duplik ein. D. Mit Verfügung vom 16. Januar 2012 wies das Bundesgericht das Gesuch des Beschwerdeführers um Gewährung der aufschiebenden Wirkung ab. 