Sachverhalt:
A. A.a X._ (Beschwerdeführer) wurde im heutigen Serbien geboren. Er war früher professioneller Fussballspieler und ist derzeit als Fussballtrainer tätig. Er wohnt in Mexico City und hat die mexikanische Staatsbürgerschaft angenommen.
Die Jamaican Football Federation (Beschwerdegegnerin) ist der nationale Fussballverband Jamaikas und als solcher Mitglied der Fédération Internationale de Football Association (FIFA; Verfahrensbeteiligte), einem Verein schweizerischen Rechts mit Sitz in Zürich.
A.b Am 1. Dezember 2006 schloss der Beschwerdeführer mit der Beschwerdegegnerin einen Arbeitsvertrag ab. Darin verpflichtete er sich, zwischen dem 15. November 2006 und dem 14. November 2010 als technischer Direktor und Cheftrainer der Nationalmannschaft von Jamaika zu wirken. Als Entgelt war ein Jahressalär von USD 1 Mio., d.h. für die vierjährige Vertragsdauer eine Gesamtsumme von USD 4 Mio., vorgesehen.
Die Pflichten des Beschwerdeführers wurden in Ziffer 5 des Arbeitsvertrags unter anderem wie folgt beschrieben:
5(1): "Be responsible for and undertake the preparation, supervision and management of All National Football Teams; the assessment, supervision and upgrading of all national coaches; and such other matters necessary for the smooth and orderly development of the sport of football in Jamaica";
5(2): "Devote his full time and best efforts to the performance of the terms of this Agreement. In this regard, the Technical Director & Head Coach of The Senior Team agrees not to engage in the provisions of any other services, or in any business or commercial activity without the prior written approval of the Federation";
5(3): "Advance the coaching methods of football teams island-wide in accordance with the National Football Programme approved by the Federation";
5(7): "Prepare and outline a plan of action for the comprehensive development of local football including all National Teams and present this to the Board of Directors of the Federation within six (6) months of the signing of this agreement."
Gemäss Ziffer 9 (2) soll der Vertrag ohne Weiteres beendet werden, falls "the Technical Director & Head Coach of the Senior Team breaches Clause 5 or 7 hereof or habitually neglects the duties he is required to perform under the term of this Agreement, and the Federation gives thirty (30) days written notice to the Technical Director & Head Coach of the Senior Team of its intention to terminate this Agreement upon the expiry of such notice." Ziffer 9(4) sieht zudem vor, dass die Beschwerdegegnerin den Arbeitsvertrag unter Einhaltung einer Kündigungsfrist von 30 Tagen auflösen kann, sofern sich die Nationalmannschaft nicht für die Weltmeisterschaft 2010 in Südafrika qualifizieren sollte.
A.c Mit Schreiben vom 7. November 2007 kündigte die Beschwerdegegnerin den Vertrag mit dem Beschwerdeführer und berief sich dabei auf die Ziffern 9(2), 5(1), 5(3) und 5(7) des Arbeitsvertrags. Sie warf dem Beschwerdeführer zusammengefasst vor, er habe es versäumt:
a) die Nationalmannschaft und andere Fussballmannschaften mit dem erforderlichen Können, Sorgfalt und Einsatz vorzubereiten, zu überwachen und zu trainieren, was zu den schlechten Resultaten beigetragen habe und womit Ziffer 5(1) des Arbeitsvertrags verletzt worden sei;
b) ein Programm zur Verbesserung der nationalen Trainer zu entwickeln, worin ebenfalls eine Verletzung von Ziffer 5(1) zu sehen sei;
c) in Übereinstimmung mit dem National Football Programme einen Plan für die Verbesserung der Trainingsmethoden der Fussballmannschaften Jamaikas zu entwickeln, womit er die Ziffer 5(3) des Arbeitsvertrags verletzt habe;
d) einen Aktionsplan für die umfassende Entwicklung des lokalen Fussballs vorzulegen, womit Ziffer 5(3) verletzt worden sei.
Die Beschwerdegegnerin erwähnte in ihrem Schreiben, sie werde dem Beschwerdeführer USD 62'500.-- als Entschädigung für die Nichteinhaltung der vertraglich vereinbarten dreissigtägigen Kündigungsfrist bezahlen, USD 330'500.-- für den bis 15. November 2007 geschuldeten Lohn für das erste Vertragsjahr sowie USD 7'553 als Spesenentschädigung, also insgesamt USD 400'553.--.
B. B.a Am 28. Februar 2008 klagte der Beschwerdeführer beim FIFA Players' Status Committee gegen die Beschwerdegegnerin und verlangte Zahlungen über USD 3 Mio. wegen ungerechtfertigter Vertragsauflösung sowie USD 1 Mio. Schadenersatz wegen der Beeinträchtigung seines Rufs.
Mit Entscheid vom 10. Februar 2010 sprach das FIFA Players' Status Committee dem Beschwerdeführer den Betrag von USD 1 Mio. wegen ungerechtfertigter Vertragsauflösung zu. Es befand insbesondere, die Beschwerdegegnerin habe keine Urkundenbeweise für die behaupteten Vertragsverletzungen beigebracht. Das Players' Status Committee erwog weiter, der Arbeitsvertrag wäre gemäss Ziffer 9(4) per 19. November 2008 aufgelöst worden, nachdem feststand, dass sich die jamaikanische Nationalmannschaft nicht für die Weltmeisterschaft 2010 qualifizieren konnte. Entsprechend stehe dem Beschwerdeführer lediglich der Lohn bis zu diesem Zeitpunkt zu und nicht bis zum Ende der verbleibenden dreijährigen Vertragsdauer. Das auf Zahlung von Schadenersatz wegen Rufschädigung lautende Rechtsbegehren wies das Players' Status Committee ab.
Mit Entscheid vom 10. Februar 2010 sprach das FIFA Players' Status Committee dem Beschwerdeführer den Betrag von USD 1 Mio. wegen ungerechtfertigter Vertragsauflösung zu. Es befand insbesondere, die Beschwerdegegnerin habe keine Urkundenbeweise für die behaupteten Vertragsverletzungen beigebracht. Das Players' Status Committee erwog weiter, der Arbeitsvertrag wäre gemäss Ziffer 9(4) per 19. November 2008 aufgelöst worden, nachdem feststand, dass sich die jamaikanische Nationalmannschaft nicht für die Weltmeisterschaft 2010 qualifizieren konnte. Entsprechend stehe dem Beschwerdeführer lediglich der Lohn bis zu diesem Zeitpunkt zu und nicht bis zum Ende der verbleibenden dreijährigen Vertragsdauer. Das auf Zahlung von Schadenersatz wegen Rufschädigung lautende Rechtsbegehren wies das Players' Status Committee ab.
B.b B.b.a Mit Eingabe vom 28. April 2010 appellierte die Beschwerdegegnerin beim Tribunal Arbitral du Sport (TAS) gegen den Entscheid des FIFA Players' Status Committee vom 10. Februar 2010. Am 10. Mai 2010 reichte sie dem TAS ihre Appellationsbegründung ein. Sie verlangte in erster Linie die Aufhebung des angefochtenen Entscheids wegen Unzuständigkeit des FIFA Players' Status Committee. Eventualiter beantragte sie, der angefochtene Entscheid vom 10. Februar 2010 sei aufzuheben, die Schadenersatzklage des Beschwerdeführers sei abzuweisen und der Beschwerdeführer sei im Gegenzug zur Zahlung von USD 500'000.-- zu verurteilen, zuzüglich Zins zu 5 % seit dem 1. Juni 2007.
Der Beschwerdeführer beantragte in erster Linie, der angefochtene Entscheid des FIFA Players' Status Committee vom 10. Februar 2010 sei zu bestätigen. Eventualiter verlangte er, die Beschwerdegegnerin sei widerklageweise zur Zahlung von USD 3 Mio. zu verurteilen.
B.b.b Mit Schreiben vom 30. Juni 2010 forderte das TAS die Parteien auf, weitere Eingaben zu bestimmten Streitfragen hinsichtlich der Zuständigkeit, der Vertragsverletzung sowie der Schadensminderung einzureichen. Im Weiteren sollten sich die Parteien dazu äussern, ob es weitere Zeugen gebe, deren Einvernahme anlässlich der mündlichen Verhandlung erforderlich sei. Die Stellungnahmen gingen am 20. bzw. 21. Juli 2010 beim TAS ein. Dazu äusserten sich die Parteien wiederum mit Eingaben vom 28. bzw. 29. Juli 2010.
Die Parteien unterzeichneten die vom TAS erlassene Anordnung über den weiteren Ablauf des Verfahrens ("Order of Procedure") am 15. bzw. 17. November 2010. Die Verhandlung fand am 22. November 2010 in Lausanne statt. Zwei Zeugen wurden telefonisch befragt.
Mit Schreiben vom 23. November 2010 forderte das TAS die Beschwerdegegnerin auf, die Protokolle ihrer zwischen Dezember 2006 und November 2007 abgehaltenen Vorstandssitzungen einzureichen und zu einigen Zeitungsartikeln sowie Medienmitteilungen Stellung zu nehmen.
Am 30. November 2010 reichte die Beschwerdegegnerin dem TAS die Protokolle der Vorstandssitzungen vom 9. Juni 2007 und 9. September 2007 ein mit dem Hinweis, dies seien die einzigen Protokolle, die sie für den massgebenden Zeitraum habe finden können. Sie äusserte sich zudem zu den im Schreiben des TAS aufgeführten Zeitungsartikeln und Pressemitteilungen und reichte im Übrigen verschiedene schriftliche Zeugenaussagen ("witness statements") ein.
Auf entsprechende Aufforderung des TAS hin, äusserte sich der Beschwerdeführer mit Schreiben vom 14. Dezember 2010 zur Eingabe der Beschwerdegegnerin. Er verlangte in seinem Schreiben zudem, es sei eine neue mündliche Verhandlung anzusetzen, in der Y._, der ehemalige Präsident der Beschwerdegegnerin, als Zeuge zu befragen sei. Das TAS lehnte dies unter Verweis auf die Verfahrensregeln von Artikel R55 und R56 des TAS Code ab. Dabei wies es darauf hin, der Beschwerdeführer habe es unterlassen, Y._ als Zeuge aufzurufen, als dies verfahrensrechtlich noch möglich gewesen sei, obwohl er mit Schreiben vom 30. Juni 2010 nochmals ausdrücklich aufgefordert worden war, allfällige zusätzliche Zeugen für die mündliche Verhandlung zu benennen. Im Weiteren könne der Präsident des Schiedsgerichts gemäss Artikel R56 nach Einreichung der Appellationsbegründung bzw. der Appellationsantwort nur in Ausnahmefällen neue Tatsachenbehauptungen oder Beweismittel zulassen; der Beschwerdeführer habe jedoch keine ausserordentlichen Umstände vorgebracht, um die Verspätung seines Beweisbegehrens zu rechtfertigen.
B.b.c Mit Schiedsentscheid vom 2. Februar 2011 hiess das TAS die Appellation der Beschwerdegegnerin gegen den Entscheid des Players' Status Committee vom 10. Februar 2010 teilweise gut (Dispositiv-Ziff. 1) und verurteilte die Beschwerdegegnerin zur Zahlung von Schadenersatz im Betrag von USD 19'691.90 an den Beschwerdeführer, dies zusätzlich zu den Beträgen (USD 62'500.-- + USD 330'500.-- + USD 7'553.--), die im Schreiben der Beschwerdegegnerin vom 7. November 2007 aufgeführt waren (Dispositiv-Ziff. 2). Im Weiteren wies das TAS die Widerklage des Beschwerdeführers auf Zahlung von USD 3 Mio. ab (Dispositiv-Ziff. 3). Schliesslich entschied es über die Kosten (Dispositiv-Ziff. 4) und Entschädigungen (Dispositiv-Ziff. 5) und wies sämtliche weiteren Begehren ab (Dispositiv-Ziff. 6).
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es seien Dispositiv-Ziff. 1-2 und 4-6 des Schiedsentscheids des TAS vom 2. Februar 2011 aufzuheben und es sei die Streitsache im entsprechenden Umfang zur neuen Entscheidung an das Schiedsgericht zurückzuweisen.
Die Beschwerdegegnerin sowie das TAS beantragen die Abweisung der Beschwerde. Die FIFA hat auf eine aktive Beteiligung am Verfahren verzichtet.

Erwägungen:
1. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Weder der Beschwerdeführer noch die Beschwerdegegnerin hatten im massgebenden Zeitpunkt ihren Wohnsitz bzw. Sitz oder ihren gewöhnlichen Aufenthalt in 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).
1.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. 3b S. 382).
1.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. 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).
Der Beschwerdeführer stellt seinen rechtlichen Vorbringen eine mehrseitige Sachverhaltsdarstellung voran, in der er die Hintergründe des Rechtsstreits sowie des Verfahrens aus eigener Sicht schildert. Er weicht darin über weite Strecken von den tatsächlichen Feststellungen der Vorinstanz ab oder erweitert diese, ohne substantiiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. Er übt zudem verschiedentlich appellatorische Kritik am angefochtenen Entscheid, ohne jedoch nach <ref-law> zulässige Rügen zu erheben. Seine Darlegungen haben insoweit unbeachtet zu bleiben.
2. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs sowie des Grundsatzes der Gleichbehandlung der Parteien (<ref-law>).
2. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs sowie des Grundsatzes der Gleichbehandlung der Parteien (<ref-law>).
2.1 2.1.1 Der Beschwerdeführer bringt vor, aus dem Gehörsanspruch folge nicht nur die Pflicht des Schiedsgerichts, die Argumente der Parteien entgegenzunehmen und bei der Entscheidfindung zu berücksichtigen, sondern auch, dass diese Eingang in die Begründung finden müssten und aus der Begründung die Überlegungen hervorzugehen hätten, von denen sich das Schiedsgericht habe leiten lassen und auf die es seinen Entscheid gestützt habe.
Das Schiedsgericht kam in Bezug auf Ziffer 5(7) des Arbeitsvertrags zum Schluss, die Vertragsbestimmung begründe richtig ausgelegt eine Verpflichtung, den Aktionsplan dem Vorstand der Beschwerdegegnerin zu unterbreiten, die durch die in den Rechtsschriften des Beschwerdeführers behaupteten - jedoch ohnehin nicht weiter belegten - Tatsachen nicht erfüllt werden könne. Der Beschwerdeführer wirft dem Schiedsgericht vor, es habe sein Argument, dass der Vorstand der Beschwerdegegnerin über die von ihm entwickelten Pläne informiert war, nicht beachtet.
2.1.2 <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).
Entgegen dem, was der Beschwerdeführer anzunehmen scheint, ergibt sich aus dem Grundsatz des rechtlichen Gehörs im Sinne von <ref-law> kein Anspruch auf Begründung des Schiedsspruchs (<ref-ruling> E. 6 S. 187 f. mit Hinweisen). Mit der angeblich unzureichenden Begründung des angefochtenen Entscheids zeigt er keinen in <ref-law> vorgesehenen Beschwerdegrund auf (vgl. <ref-ruling> E. 6.1 S. 187; <ref-ruling> E. 2b S. 577 f.; je mit Hinweisen). Entgegen der in der Beschwerde vertretenen Ansicht trifft es zudem nicht zu, dass das TAS das Argument der angeblichen Kenntnisnahme des Verbandsvorstands unbeachtet gelassen hätte. Zum einen hat es in tatsächlicher Hinsicht festgehalten, die Beschwerdegegnerin habe Beweise für den Umstand beigebracht, dass dem Verbandsvorstand kein Aktionsplan präsentiert wurde, während der Beschwerdeführer keinen Gegenbeweis erbracht habe. Zum anderen erwog es, aus den Behauptungen des Beschwerdeführers, die im Übrigen unbewiesen seien, lasse sich nicht schliessen, dass er seiner vertraglichen Pflicht, den Aktionsplan dem Vorstand zu präsentieren, nachgekommen wäre.
Das Schiedsgericht genügt damit der sich aus dem Grundsatz des rechtlichen Gehörs (<ref-law>) ergebenden Mindestanforderung, die entscheiderheblichen Probleme zu prüfen und zu behandeln (vgl. <ref-ruling> E. 5.2 S. 248). Davon, dass dem Beschwerdeführer ein richterliches Versehen verunmöglicht hätte, seinen Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen (vgl. <ref-ruling> E. 5.2 S. 248; <ref-ruling> E. 2f S. 580), kann keine Rede sein. Mit seinen Vorbringen übt er vielmehr inhaltliche Kritik am angefochtenen Schiedsentscheid; er macht jedoch zu Recht nicht geltend, dieser verstosse gegen den Ordre public (<ref-law>).
Das Schiedsgericht genügt damit der sich aus dem Grundsatz des rechtlichen Gehörs (<ref-law>) ergebenden Mindestanforderung, die entscheiderheblichen Probleme zu prüfen und zu behandeln (vgl. <ref-ruling> E. 5.2 S. 248). Davon, dass dem Beschwerdeführer ein richterliches Versehen verunmöglicht hätte, seinen Standpunkt in Bezug auf ein prozessrelevantes Thema in den Prozess einzubringen (vgl. <ref-ruling> E. 5.2 S. 248; <ref-ruling> E. 2f S. 580), kann keine Rede sein. Mit seinen Vorbringen übt er vielmehr inhaltliche Kritik am angefochtenen Schiedsentscheid; er macht jedoch zu Recht nicht geltend, dieser verstosse gegen den Ordre public (<ref-law>).
2.2 2.2.1 Der Beschwerdeführer rügt weiter, das Schiedsgericht habe seine Ausführungen betreffend den wirklichen Kündigungsgrund der Beschwerdegegnerin in Verletzung des Gehörsanspruchs nicht beachtet, obwohl er im Schiedsverfahren mehrmals darauf hingewiesen habe, dass die am 7. November 2007 erfolgte fristlose Kündigung nur darauf zurückzuführen sei, dass vier Tage vorher der damalige Präsident der Beschwerdegegnerin abgesetzt und durch Z._ ersetzt wurde. Die von der Beschwerdegegnerin geltend gemachten Gründe für die erfolgte fristlose Vertragsauflösung seien bloss vorgeschoben gewesen.
2.2.2 Das Schiedsgericht hat die Vorbringen des Beschwerdeführers zur Frage der gehörigen Vertragserfüllung zusammengefasst. Es hat dabei ausdrücklich erwähnt, der Beschwerdeführer mache geltend, dass er seine Vertragspflichten erfüllt und die Beschwerdegegnerin den Arbeitsvertrag verletzt habe, indem sie vorgebe, diesen nach Ziffer 9 zu kündigen. Der Beschwerdeführer behaupte, so das Schiedsurteil weiter, er sei nicht wegen mangelhafter Erfüllung seiner vertraglichen Pflichten entlassen worden, sondern infolge des am 3. November 2007 erfolgten Wechsels im Präsidium der Beschwerdegegnerin, als Y._ durch Z._ ersetzt worden sei.
Es kann angesichts dieser Ausführungen im angefochtenen Entscheid nicht die Rede davon sein, das Schiedsgericht habe das vom Beschwerdeführer vorgebrachte Argument nicht zur Kenntnis genommen. Vielmehr hat das TAS den Einwand, die Kündigungsgründe seien bloss vorgeschoben worden, in seinem Entscheid berücksichtigt. Indem es eine Verletzung von Ziffer 5(7) des Arbeitsvertrags durch den Beschwerdeführer bejahte und die ausgesprochene Kündigung für zulässig erachtete, wies es den Einwand sinngemäss als unbehelflich zurück. Einer ausdrücklichen Begründung bedurfte es dazu nicht (vgl. <ref-ruling> E. 6 S. 187 f.). Die Rüge der Missachtung des rechtlichen Gehörs (<ref-law>) erweist sich als unbegründet.
Es kann angesichts dieser Ausführungen im angefochtenen Entscheid nicht die Rede davon sein, das Schiedsgericht habe das vom Beschwerdeführer vorgebrachte Argument nicht zur Kenntnis genommen. Vielmehr hat das TAS den Einwand, die Kündigungsgründe seien bloss vorgeschoben worden, in seinem Entscheid berücksichtigt. Indem es eine Verletzung von Ziffer 5(7) des Arbeitsvertrags durch den Beschwerdeführer bejahte und die ausgesprochene Kündigung für zulässig erachtete, wies es den Einwand sinngemäss als unbehelflich zurück. Einer ausdrücklichen Begründung bedurfte es dazu nicht (vgl. <ref-ruling> E. 6 S. 187 f.). Die Rüge der Missachtung des rechtlichen Gehörs (<ref-law>) erweist sich als unbegründet.
2.3 2.3.1 Der Beschwerdeführer rügt eine Verletzung des Grundsatzes der Gleichbehandlung der Parteien sowie des Gehörsanspruchs (<ref-law>) durch das Schiedsgericht, die er darin sieht, dass der Beschwerdegegnerin zur Frage der Verletzung von Ziffer 5(7) des Arbeitsvertrags Gelegenheit zur nachträglichen Vorlage weiterer Beweismittel gegeben worden, während dem Beschwerdeführer zum gleichen Thema eine zusätzliche Beweisführung in Form einer Zeugenbefragung von Y._ verwehrt worden sei. Das Schiedsgericht dürfe dem Beschwerdeführer nicht das verweigern (nachträgliche Nennung von Beweismitteln; nachträgliche Benennung eines weiteren Zeugen), was es der anderen Partei in der gleichen Situation soeben zugestanden habe. Mit der Ablehnung des Antrags auf Durchführung einer zweiten mündlichen Verhandlung und Einvernahme von Y._ als Zeuge habe das TAS den Anspruch des Beschwerdeführers auf Gleichbehandlung sowie den Anspruch auf rechtliches Gehör verletzt.
2.3.2 Unbegründet ist zunächst der Vorwurf der Gehörsverletzung. Ein Anspruch auf Beweisabnahme besteht nur, sofern der Beweisantrag rechtzeitig und formgültig erfolgte (<ref-ruling> E. 1b S. 389; vgl. auch <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2b S. 56; <ref-ruling> E. 2 S. 242; je mit Hinweisen). Der Antrag des Beschwerdeführers auf Einvernahme eines neuen Zeugen erfolgte nach den auf das Schiedsverfahren anwendbaren Verfahrensbestimmungen verspätet. Das Schiedsgericht hat daher den Gehörsanspruch des Beschwerdeführers nicht verletzt, wenn es den erst mit Schreiben vom 14. Dezember 2010 gestellten Antrag auf Einvernahme von Y._ als Zeugen gestützt auf Artikel R55 und R56 des TAS Code abwies.
2.3.3 Der Grundsatz der Gleichbehandlung der Parteien verlangt vom Schiedsgericht insbesondere, die Parteien grundsätzlich in allen Verfahrensfragen gleich zu behandeln (FRANK VISCHER, in: Zürcher Kommentar, 2. Aufl. 2004, N. 25 zu <ref-law>; BERNARD DUTOIT, Commentaire de la loi fédérale du 18 décembre 1987, 4. Aufl. 2005, N. 6 zu <ref-law>).
Auch aus diesem Grundsatz lässt sich kein Anspruch des Beschwerdeführers auf nachträgliche Durchführung einer zweiten mündlichen Verhandlung sowie auf Einvernahme von Y._ als Zeuge ableiten. Der Beschwerdeführer gibt die Verfahrensanordnung des TAS vom 23. November 2010 zunächst ungenau wieder, wenn er in allgemeiner Weise behauptet, damit sei der Beschwerdegegnerin die Gelegenheit gegeben worden, zur Frage der Verletzung von Ziffer 5(7) des Arbeitsvertrags nachträglich Beweismittel zu nennen bzw. weitere Beweismittel vorzubringen. Vielmehr forderte das TAS die Beschwerdegegnerin mit besagtem Schreiben auf, bestimmte Dokumente (nämlich die Protokolle ihrer zwischen Dezember 2006 und November 2007 abgehaltenen Vorstandssitzungen) einzureichen und sich zu bestimmten Zeitungsartikeln sowie Medienmitteilungen zu äussern.
Entgegen dem, was der Beschwerdeführer anzunehmen scheint, kann darin keine Einladung an die Beschwerdegegnerin erblickt werden, beliebige neue Beweismittel zum Thema der Verletzung von Ziffer 5(7) des Arbeitsvertrags einzureichen oder gar neue Beweismassnahmen in Form von Zeugeneinvernahmen zu beantragen. Eine weitere Zeugenbefragung wurde denn auch weder beantragt noch angeordnet. Entsprechend gebot der Grundsatz der Gleichbehandlung der Parteien nicht, jeglichen neuen Beweisanträgen des Beschwerdeführers, so insbesondere dem Antrag auf Einvernahme eines neuen Zeugen, stattzugeben, geschweige denn, eine zweite mündliche Verhandlung durchzuführen. Der Beschwerdeführer bestreitet zu Recht nicht, dass er zur entsprechenden Eingabe der Beschwerdegegnerin Stellung nehmen konnte. Die Begründung im angefochtenen Entscheid für die Abweisung des Beweisantrags, dass nämlich gemäss Artikel R55 des TAS Code Zeugen in der Appellationsantwort zu benennen sind und der Beschwerdeführer weder in seiner Appellationsantwort noch auf ausdrückliche Aufforderung des Schiedsgerichts vom 30. Juni 2010 im Hinblick auf die mündliche Verhandlung hin die Einvernahme von Y._ verlangt und sich im Übrigen auch in seiner Eingabe vom 14. Dezember 2010 nicht auf ausserordentliche Umstände für eine nachträgliche Zulassung von Beweisanträgen gemäss Artikel R56 des TAS Code berufen habe, verletzt die zwingenden Verfahrensgrundsätze von <ref-law> nicht.
Aus dem Grundsatz auf Gleichbehandlung lässt sich kein Anspruch des Beschwerdeführers auf nachträgliche Durchführung einer zweiten mündlichen Verhandlung und auf Einvernahme von Y._ als Zeuge ableiten.
3. 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).
Da die Beschwerdegegnerin erst in ihrer Beschwerdeantwort um Sicherstellung der Parteikosten ersucht hat, waren ihr im Zeitpunkt der Gesuchstellung sämtliche Parteikosten bereits entstanden, so dass das Gesuch als gegenstandslos abzuschreiben ist (<ref-ruling> E. 2 S. 88).

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