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. 