Sachverhalt: A. A.a Francelino da Silva Matuzalem, Rom, (Beschwerdeführer), geboren am 10. Juni 1980, ist ein professioneller Fussballspieler brasilianischer Nationalität. Er spielt derzeit beim Fussballclub SS Lazio Spa in Rom. Die Fédération Internationale de Football Association (FIFA; Beschwerdegegnerin) ist ein Verein schweizerischen Rechts (Art. 60 ff. ZGB) mit Sitz in Zürich. Real Saragossa SAD ist ein spanischer Fussballclub. Er ist Mitglied des spanischen Fussballverbands, der wiederum der FIFA angehört. A.b Am 26. Juni 2004 schloss der Beschwerdeführer mit dem ukrainischen Fussballclub FC Shakhtar Donetsk einen Arbeitsvertrag für die Zeit vom 1. Juli 2004 bis 1. Juli 2009 ab. Am 2. Juli 2007 löste der Beschwerdeführer seinen Arbeitsvertrag mit dem FC Shakhtar Donetsk fristlos und weder aus wichtigem Grund ("just cause") noch aus sportlich triftigen Gründen ("sporting just cause") auf. Mit Schreiben vom 16. Juli 2007 verpflichtete sich Real Saragossa SAD dem Beschwerdeführer gegenüber, ihn für allfällige Ersatzansprüche infolge der vorzeitigen Vertragsauflösung schadlos zu halten. Am 19. Juli 2007 unterzeichnete der Beschwerdeführer einen neuen Arbeitsvertrag mit Real Saragossa SAD und verpflichtete sich für die nächsten drei Spielsaisons bis 30. Juni 2010. Am Ende der Spielsaison 2007/2008 stieg die Mannschaft von Real Saragossa SAD in die zweite spanische Fussballliga ab. Mit Vereinbarung vom 17. Juli 2008 transferierte Real Saragossa SAD den Beschwerdeführer für die Spielsaison 2008/2009 vorübergehend an den Fussballclub SS Lazio Spa in Rom. Am 22. Juli 2008 stimmte der Beschwerdeführer diesem zeitweiligen Transfer zu und schloss mit dem italienischen Club einen Arbeitsvertrag für den Zeitraum vom 22. Juli 2008 bis 20. Juni 2011 ab. Am Ende der Spielsaison 2008/2009 stieg Real Saragossa SAD wieder in die erste Liga auf. Am 23. Juli 2009 stimmte Real Saragossa SAD dem endgültigen Transfer des Beschwerdeführers zum Fussballclub SS Lazio Spa gegen eine Transfersumme von EUR 5.1 Mio. zu. Am gleichen Tag schloss der SS Lazio Spa mit dem Beschwerdeführer einen neuen Arbeitsvertrag ab, der denjenigen vom 22. Juli 2008 ablöste und eine feste Vertragsdauer bis 30. Juni 2014 sowie ein Salär von EUR xxx netto pro Saison (zuzüglich nicht näher bestimmter Spielboni) vorsah. A.c Mit Entscheid vom 2. November 2007 sprach die Kammer zur Beilegung von Streitigkeiten der FIFA ("Dispute Resolution Chamber") dem Fussballclub FC Shakhtar Donetsk infolge der vertragswidrigen Kündigung Schadenersatz im Betrag von EUR 6.8 Mio. zu, zuzüglich Verzugszins zu 5 % nach Ablauf von 30 Tagen ab Entscheidfällung. Mit Schiedsentscheid vom 19. Mai 2009 hob das Tribunal Arbitral du Sport (TAS) den Entscheid vom 2. November 2007 teilweise auf und verpflichtete den Beschwerdeführer sowie den Fussballclub Real Saragossa SAD solidarisch zur Zahlung von EUR 11'858'934.-- zuzüglich Zins zu 5 % seit dem 5. Juli 2007. Eine vom Beschwerdeführer und Real Saragossa SAD gegen den Schiedsentscheid des TAS vom 19. Mai 2009 erhobene Beschwerde in Zivilsachen wies das Bundesgericht mit Urteil vom 2. Juni 2010 ab, soweit es darauf eintrat. B. B.a Am 14. Juli 2010 informierte der stellvertretende Sekretär der Disziplinarkommission ("Disciplinary Committee") der FIFA den Beschwerdeführer und Real Saragossa SAD darüber, (a) dass gegen sie ein Disziplinarverfahren eingeleitet werde, weil sie dem Entscheid des TAS vom 19. Mai 2009 keine Folge geleistet hätten, (b) dass entsprechend Sanktionen nach Art. 64 des FIFA-Disziplinarreglements ("Disciplinary Code" [Ausgabe 2009]) verhängt würden, und (c) dass der Fall anlässlich der nächsten Sitzung der Disziplinarkommission beurteilt werde. Das damals anwendbare FIFA-Disziplinarreglement (Ausgabe 2009) sah unter anderem Folgendes vor: "Article 22 Ban on taking part in any football-related activity A person may be banned from taking part in any kind of football-related activity (administrative, sports or any other). A person may be banned from taking part in any kind of football-related activity (administrative, sports or any other). ... Section 8. Failure to respect decisions Article 64 [only] 1. Anyone who fails to pay another person (such as a player, a coach or a club) or FIFA a sum of money in full or part, even though instructed to do so by a body, a committee or an instance of FIFA or CAS (financial decision), or anyone who fails to comply with another decision (non-financial decision) passed by a body, a committee or an instance of FIFA or CAS: a) will be fined at least CHF 5,000 for failing to comply with a decision; b) will be granted a final deadline by the judicial bodies of FIFA in which to pay the amount due or to comply with the (non-financial) decision; c) (only for clubs:) will be warned and notified that, in the case of default or failure to comply with a decision within the period stipulated, points will be deducted or demotion to a lower division ordered. A transfer ban may also be pronounced. 2. If the club disregards the final time limit, the relevant association shall be requested to implement the sanctions threatened. 3. If points are deducted, they shall be proportionate to the amount owed. 4. A ban on any football-related activity may also be imposed against natural persons. ..." Am 26. Juli 2010 teilte Real Saragossa SAD der Disziplinarkommission mit, er befinde sich in ernsthaften finanziellen Schwierigkeiten, die zur Insolvenz bzw. zum Konkurs führen könnten; die Voraussetzungen für eine Sanktion nach Art. 64 des FIFA-Disziplinarreglements seien nicht erfüllt, da sich der Club um eine Begleichung der Schuld bemühe. Am 20. August 2010 schickte der Beschwerdeführer der Disziplinarkommission je eine Kopie seines Schreibens vom 19. August 2010, mit dem er Real Saragossa SAD zur Zahlung des ausstehenden Betrags an FC Shakhtar Donetsk aufgefordert hatte, und der bereits erwähnten Schadloshaltungserklärung von Real Saragossa SAD vom 16. Juli 2007. Mit Entscheid vom 31. August 2010 sprach die Disziplinarkommission den Beschwerdeführer und den Fussballclub Real Saragossa SAD schuldig, ihre Verpflichtungen gemäss dem Schiedsentscheid des TAS vom 19. Mai 2009 nicht erfüllt zu haben (Dispositiv-Ziffer 1). Im Weiteren verurteilte sie den Beschwerdeführer gestützt auf Art. 64 des FIFA-Disziplinarreglements solidarisch mit dem Club zu einer Busse von Fr. 30'000.-- (Dispositiv-Ziffer 2) und räumte ihm eine letzte Frist von 90 Tagen zur Bezahlung der Forderung ein (Dispositiv-Ziffer 3), verbunden mit der Androhung, im Falle des Ausbleibens der Zahlung werde dem Beschwerdeführer auf einfache Aufforderung des Gläubigers FC Shakhtar Donetsk hin jegliche in Zusammenhang mit dem Fussball stehende Tätigkeit verboten, ohne dass ein weiterer Entscheid der Disziplinarkommission erforderlich wäre (Dispositiv-Ziffer 4): "4. If payment is not made by this deadline, the creditor may demand in writing from FIFA that a ban on taking part in any football related activity be imposed on the player Matuzalem Francelino da Silva and/or six (6) points be deducted from the first team of the club Real Zaragoza SAD in the domestic league championship. Once the creditor has filed this/these requests, the ban on taking part in any football-related activity will be imposed on the player Matuzalem Francelino da Silva and/or the points will be deducted automatically from the first team of the club Real Zaragoza SAD without further formal decisions having to be taken by the FIFA Disciplinary Committee. The association(s) concerned will be informed of the ban on taking part in any football-related activity. Such ban will apply until the total outstanding amount has been fully paid. ..." Am 1. September 2010 überwies Real Saragossa SAD EUR 500'000.-- auf ein im Namen des FC Shakhtar Donetsk eröffnetes Bankkonto. Weitere Zahlungen seitens Real Saragossa SAD oder des Beschwerdeführers blieben aus. B.b Sowohl der Beschwerdeführer als auch Real Saragossa SAD erhoben gegen den Entscheid der FIFA-Disziplinarkommission vom 31. August 2010 Berufung beim Tribunal Arbitral du Sport (TAS). Mit Schiedsurteil vom 29. Juni 2011 wies das TAS die Berufungen von Real Saragossa SAD (Dispositiv-Ziffer 1) und des Beschwerdeführers (Dispositiv-Ziffer 2) ab und bestätigte den Entscheid der Disziplinarkommission der FIFA vom 31. August 2010 (Dispositiv-Ziffer 3). Es wies zudem alle weiteren Anträge ab (Dispositiv-Ziffer 4) und regelte die Kosten des Verfahrens (Dispositiv-Ziffern 5 und 6). C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsentscheid des TAS vom 29. Juni 2011 aufzuheben. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das TAS hat auf eine Vernehmlassung verzichtet. D. Mit Verfügung vom 24. Oktober 2011 erteilte das Bundesgericht der Beschwerde aufschiebende Wirkung. E. Der Beschwerdeführer reichte dem Bundesgericht am 25. Januar 2012 eine Replik, die Beschwerdegegnerin am 10. Februar 2012 eine Duplik ein. Mit Eingabe vom 29. Februar 2012 liess der Beschwerdeführer dem Bundesgericht im Weiteren einen Telefax der Beschwerdegegnerin vom 24. Februar 2012 betreffend das inzwischen gegen den Fussballclub Real Saragossa SAD eingeleitete Insolvenzverfahren zukommen.