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.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel derjenigen des angefochtenen Entscheids. Wurde dieser Entscheid in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht verschiedener Sprachen bedienen, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde.
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 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.3 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).
3. Der Beschwerdeführer bringt vor, das Schiedsgericht habe sich zu Unrecht für zuständig erklärt (<ref-law>), da es sich bei der beurteilten Angelegenheit um eine nicht schiedsfähige Streitsache handle.
3.1 Er bringt hierzu vor, er habe bereits im Schiedsverfahren darauf hingewiesen, dass nach Art. 49 Abs. 1 des serbischen Gesetzes über das Internationale Privatrecht zwei Parteien nur dann eine Zuständigkeit eines ausländischen Gerichts vereinbaren könnten, wenn mindestens eine von ihnen eine ausländische natürliche oder juristische Person sei.
Im zu beurteilenden Fall seien beide Parteien in der Republik Serbien domiziliert, wie sich aus der ersten Seite des Arbeitsvertrags ohne weiteres ergebe. Die Vereinbarung eines ausländischen (Schieds-)Gerichts sei diesen somit nach zwingendem serbischem Recht verboten, weshalb sie für Streitigkeiten aus ihrem Arbeitsvertrag kein ausländisches Schiedsgericht hätten vereinbaren können. Die zu beurteilende Angelegenheit beschlage eine ausschliesslich interne serbische Streitsache; beide Parteien hätten ihren Sitz bzw. Wohnsitz "zur fraglichen Zeit" in Serbien gehabt, "und der Hintergrund - die Ausübung des Amtes als Trainer der serbischen Fussball-Nationalmannschaft durch den Beschwerdegegner - könnte trotz internationaler Turniere 'serbischer' nicht sein".
Im Übrigen stehe ausser Zweifel, dass der angefochtene Schiedsentscheid zufolge klarer Verletzung von Art. 49 Abs. 1 des serbischen IPR-Gesetzes aufgrund von Art. V(1) (a) und V(2) (a) des New Yorker Übereinkommens über die Anerkennung und Vollstreckung ausländischer Schiedssprüche (SR 0.277.12) in Serbien nicht vollstreckbar sein werde. Mit einem nicht vollstreckbaren Schiedsentscheid sei keiner der Parteien gedient; damit würde der Grundsatz verletzt, dass ein (Schieds-)Gerichtsverfahren den Parteien eine effektive Justiz, d.h. eine tatsächliche Lösung ihres Streits, bringen müsse.
3.2 Der Einwand der mangelnden Schiedsfähigkeit der Streitsache ist im Rahmen der Zuständigkeitsbeschwerde (<ref-law>) zu prüfen (BGE <ref-ruling> E. 5 S. 141; <ref-ruling> E. 3a S. 355). 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 mit Hinweisen). Zu beachten ist im Weiteren, dass der Einwand der fehlenden Schiedsfähigkeit nach der bundesgerichtlichen Rechtsprechung - wie die Einrede der Unzuständigkeit (vgl. <ref-law>) - im frühest möglichen Zeitpunkt und vor der Einlassung auf die Hauptsache zu erheben ist; andernfalls ist eine entsprechende Rüge vor Bundesgericht nicht mehr zulässig (Urteile 4A_370/2007 vom 21. Februar 2008 E. 5.2.2; 4P.217/1992 vom 15. März 1993 E. 5, nicht publ. in <ref-ruling>).
3.3 Die Vorbringen des Beschwerdeführers, mit denen er die angeblich fehlende Schiedsfähigkeit der Streitsache begründet, lassen sich - worauf in der Beschwerdeantwort zutreffend hingewiesen wird - nicht auf den im angefochtenen Schiedsentscheid verbindlich festgestellten Sachverhalt stützen. Das Schiedsurteil hält lediglich fest, dass der Beschwerdegegner seinen gesetzlichen Wohnsitz seit 30 Jahren in Spanien habe und führt diesen auch im Rubrum auf. Dem angefochtenen Entscheid lassen sich keine tatsächlichen Feststellungen entnehmen, die auf einen serbischen Wohnsitz des Beschwerdegegners zu einem bestimmten Zeitpunkt, geschweige denn im Zeitpunkt des Vertragsschlusses schliessen liessen. Soweit der Beschwerdeführer vor Bundesgericht behauptet, dies ergebe sich aus dem unterzeichneten Vertragsdokument, ist er nicht zu hören, zumal er diese Behauptung nicht mit einer Sachverhaltsrüge verbindet. Der Beschwerdeführer zeigt im Übrigen auch nicht auf, inwiefern er sich im Schiedsverfahren auf den Umstand des angeblichen Wohnsitzes des Beschwerdegegners in Serbien berufen und gestützt darauf die Schiedsfähigkeit bestritten hätte.
Auf das Vorbringen des Beschwerdeführers, aufgrund des serbischen Wohnsitzes des Beschwerdegegners "zur fraglichen Zeit" sei das TAS unter Berücksichtigung von Art. 49 Abs. 1 des serbischen IPR-Gesetzes mangels Schiedsfähigkeit nicht zuständig gewesen, kann nicht eingetreten werden.
3.4 Die Rüge der fehlenden Schiedsfähigkeit wäre ohnehin unbegründet. Nachdem er sich im Schiedsverfahren noch darauf berufen hat, es sei den Parteien verwehrt, ihre Streitigkeit vor ein Schiedsgericht zu bringen, da ein Rechtsstreit aus einem Arbeitsverhältnis zwingend von einem staatlichen Gericht zu beurteilen sei, bestreitet er die Schiedsfähigkeit arbeitsrechtlicher Streitigkeiten im bundesgerichtlichen Beschwerdeverfahren zu Recht nicht mehr (vgl. <ref-ruling> E. 4.2 S. 470 f.) und bestätigt überdies, dass solche Streitigkeiten auch nach serbischem Recht schiedsfähig seien. Er bringt auch nicht etwa vor, der Beschwerdegegner oder er selbst sei nach serbischem Recht nicht parteifähig bzw. generell nicht fähig, in einem gerichtlichen oder schiedsgerichtlichen Verfahren Partei zu sein; vielmehr beruft er sich darauf, als "reiner Binnensachverhalt" könne die vorliegende Angelegenheit nach serbischem Recht nicht einem ausländischen Schiedsgericht zur Beurteilung unterbreitet werden. Indem er seinen Einwand damit begründet, die konkrete Streitigkeit weise keinerlei Bezugspunkte zu einem anderen Land oder einer anderen Rechtsordnung auf, beruft er sich auf bestimmte Eigenschaften der Streitsache. Ob solche die Schiedsfähigkeit ausschliessen, beurteilt sich - wie bereits das TAS zutreffend erkannt hat und auch der Beschwerdeführer nicht grundsätzlich in Abrede stellt - nach <ref-law>.
Die erwähnte Bestimmung enthält eine materielle Regelung der Schiedsfähigkeit; auf die Aufnahme einer Kollisionsnorm hat der Gesetzgeber bewusst verzichtet, um die mit einer solchen Lösung verbundenen Schwierigkeiten bei der Bestimmung des anwendbaren Rechts zu vermeiden (BGE <ref-ruling> E. 3a S. 355). Dass es sich bei der vom TAS beurteilten Schiedsklage auf Zahlung von Schadenersatz infolge einer Verletzung des Arbeitsvertrags um einen vermögensrechtlichen Anspruch im Sinne von <ref-law> handelt, stellt der Beschwerdeführer zu Recht nicht in Frage. Soweit diese Bestimmung nach den Voraussetzungen von <ref-law> anwendbar ist, lässt sich die Schiedsfähigkeit nicht mit dem Argument in Abrede stellen, es liege aus der Sicht eines anderen Staats ein reiner Binnensachverhalt vor. Zwar hat das Bundesgericht in seiner Rechtsprechung die Möglichkeit in Betracht gezogen, die Schiedsfähigkeit einer konkreten Angelegenheit gegebenenfalls zu verneinen, sofern ausländische Bestimmungen zwingend die staatliche Gerichtsbarkeit vorschreiben und deren Berücksichtigung unter dem Blickwinkel des Ordre public (<ref-law>) geboten ist (BGE <ref-ruling> E. 3c S. 357; Urteil 4A_370/2007 vom 21. Februar 2008 E. 5.2.2). Dass dies angesichts der von ihm ins Feld geführten Bestimmung des serbischen IPR-Gesetzes der Fall wäre, zeigt der Beschwerdeführer jedoch nicht auf. Er bringt im Gegenteil vor, die vorliegende Streitigkeit könne auch von einem serbischen Schiedsgericht beurteilt werden; ausgeschlossen sei nach zwingendem serbischem Recht lediglich die Beurteilung durch ein ausländisches Gericht oder Schiedsgericht. Der Beschwerdeführer vermag keine Verletzung eines Rechtsgrundsatzes aufzuzeigen, der dem Ordre public angehört (vgl. <ref-ruling> E. 2.2.1 mit Hinweisen; Urteil 4A_558/2011 vom 27. März 2012 E. 4.1, zur Publikation vorgesehen), und im konkreten Fall eine Beurteilung des Rechtsstreits durch das TAS aufgrund der Bezugspunkte zu einem bestimmten Staat ausschliessen würde.
Dem Beschwerdeführer kann auch nicht gefolgt werden, wenn er vorbringt, es sei die angeblich fehlende Vollstreckbarkeit des angefochtenen Schiedsentscheids des TAS in der Republik Serbien zu berücksichtigen. Dass Entscheide internationaler Schiedsgerichte mit Sitz in der Schweiz, die gestützt auf <ref-law> einen Streitgegenstand als schiedsfähig erachtet haben, in einem bestimmten Land gegebenenfalls nicht vollstreckt werden können, ist nach dem Willen des Gesetzgebers, der sich ganz bewusst für eine materielle Regelung der Schiedsfähigkeit ausgesprochen hat, hinzunehmen (BGE <ref-ruling> E. 3c S. 357 und E. 3d S. 358).
4. Der Beschwerdeführer rügt hinsichtlich der Anwendung des schweizerischen Rechts durch das Schiedsgericht eine Verletzung des Ordre public (<ref-law>).
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Grundsätzen gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot, der Schutz von Handlungsunfähigen und das Verbot übermässiger Bindung (vgl. <ref-law>), wenn diese eine offensichtliche und schwerwiegende Persönlichkeitsverletzung darstellt. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff. mit Hinweisen; Urteil 4A_558/2011 vom 27. März 2012 E. 4.1 sowie E. 4.3.1 und 4.3.2, zur Publikation vorgesehen).
4.2 Der Beschwerdeführer verkennt den Begriff des Ordre public, wenn er dem Schiedsgericht vorwirft, es habe willkürlich angenommen, die Parteien hätten sich auf die Anwendung des schweizerischen Rechts geeinigt, es wende <ref-law> unzutreffend an oder seine Erwägungen stünden im Widerspruch zu den eigenen Feststellungen. Weder ist der Ordre public mit Willkür gleichzusetzen (<ref-ruling> E. 2.2.2 S. 393) noch bezweckt der Beschwerdegrund nach <ref-law>, die fehlende bzw. unzutreffende Anwendung des in der Sache anwendbaren Rechts (<ref-ruling> E. 2.2.2 S. 394) oder einen inneren Widerspruch in der Begründung des Urteils zu sanktionieren (Urteile 4A_320/2009 vom 2. Juni 2010 E. 4.3; 4A_612/2009 vom 10. Februar 2010 E. 6.2.2; 4A_464/2009 vom 15. Februar 2010 E. 5.1).
Der Beschwerdeführer zeigt auch keine Missachtung des Grundsatzes von Treu und Glauben auf, mit der eine Ordre public-Widrigkeit begründet werden könnte, wenn er in appellatorischer Weise vorbringt, die konkrete Vereinbarung der Parteien in Ziffer 13 des Arbeitsvertrags vom 16. Dezember 2009 könne entgegen dem angefochtenen Entscheid nicht als Zustimmung zur Anwendung des Schweizer Rechts interpretiert werden. Im Übrigen wirft er dem Schiedsgericht lediglich eine unzutreffende Anwendung von <ref-law> vor, zeigt jedoch nicht auf, inwiefern die Annahme einer indirekten Rechtswahl der Parteien zugunsten des schweizerischen Rechts, die sich gemäss dem angefochtenen Entscheid aus der von den Parteien gewählten Schiedsordnung - konkret R45 des TAS-Code - ergibt, gegen einen Rechtsgrundsatz verstösst, der zur wesentlichen, weitgehend anerkannten Wertordnung gehört, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte.
Entgegen der in der Beschwerde vertretenen Ansicht lässt auch der Umstand, dass Ziffer 13 des Arbeitsvertrags alternativ die Zuständigkeit weiterer Institutionen vorsieht, deren Verfahrensordnungen keine R45 TAS-Code entsprechende Bestimmung über die Anwendbarkeit des schweizerischen Rechts kennen, womit sich das auf einen konkreten Rechtsstreit anwendbare Recht womöglich je nach angerufener Instanz unterscheidet, nicht auf eine Missachtung des Ordre public durch das Schiedsgericht schliessen. Nach der erwähnten Vertragsbestimmung stand die Wahl der konkreten Schiedsinstitution ausdrücklich der klagenden Partei zu. Die vom Beschwerdeführer ins Feld geführte Unsicherheit hinsichtlich des anwendbaren Rechts liegt in der von den Parteien konkret vereinbarten Regelung begründet, insbesondere der fehlenden direkten Rechtswahl. Der Vorwurf, das Schiedsgericht habe den Grundsatz von Treu und Glauben missachtet, ist nicht gerechtfertigt.
Die Rüge, der angefochtene Schiedsentscheid sei mit dem Ordre public unvereinbar (<ref-law>), ist unbegründet.
5. Der Beschwerdeführer rügt, das Schiedsgericht habe über einen Streitpunkt entschieden, der ihm nicht unterbreitet worden sei (<ref-law>).
5.1 Er bringt vor, das Schiedsgericht habe dem Beschwerdegegner mit Dispositiv-Ziffer 3 seines Entscheids die Summe von EUR 300'000.-- zuzüglich Zins seit dem 15. September 2010 zugesprochen, mithin einen Betrag in Euro. Verlangt habe der Beschwerdegegner im Schiedsverfahren jedoch eine Zahlung in serbischen Dinar. Damit verletze der Schiedsentscheid den Grundsatz "ne eat iudex ultra petita partium".
5.2 Gemäss <ref-law> kann entsprechend der französischen Fassung des Gesetzestextes gegen einen Schiedsentscheid eingewendet werden, das Schiedsgericht habe einer Partei mehr oder anderes zugesprochen, als verlangt worden sei (<ref-ruling> E. 3a S. 642). Das Rechtsbegehren im Zusammenhang mit der vertraglich vereinbarten Marketinggebühr lautete auf Zahlung von EUR 300'000.--, zu überweisen in serbischen Dinar ("EUR 300,000 in Dinar counter value"). Das Schiedsgericht erwog, dass die "marketing fee" nach Ziffer 9 des Arbeitsvertrags in Euro geschuldet und - im Gegensatz zum Lohn - auch in dieser Währung zahlbar sei, weshalb eine Umrechnung in Landeswährung ausser Betracht falle. Nachdem der Beschwerdegegner die Zahlung von EUR 300'000.-- beantragt hatte, kann dem Schiedsgericht nicht vorgeworfen werden, sein Schiedsspruch sei nicht mehr vom Rechtsbegehren gedeckt, wenn es den geforderten Euro-Betrag zusprach, wenn auch ohne die zusätzlich beantragte Umrechnung.
Entgegen der in der Beschwerde vertretenen Ansicht hat das Schiedsgericht dem Beschwerdegegner weder mehr noch anderes zugesprochen, als dieser verlangte. Der Vorwurf, das TAS habe die in <ref-law> verankerten Grundsätze missachtet, ist ungerechtfertigt.
6. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

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