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 (<ref-law>) 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.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache redigiert, verwendet das Bundesgericht die von den Parteien gewählte Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht der deutschen Sprache bedienen, ergeht der Entscheid des Bundesgerichts auf Deutsch.
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. Der Beschwerdeführer hatte im relevanten Zeitpunkt seinen 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 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Der Antrag des Beschwerdeführers auf Aufhebung des angefochtenen Entscheids des TAS vom 29. Juni 2011 ist hinreichend und hier auch allein angebracht.
2.3 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).
Der Beschwerdeführer bringt vor, der angefochtene Entscheid verletze das rechtliche Gehör (<ref-law>) und den Ordre public (<ref-law>). Er bringt damit zulässige Rügen vor. Allerdings legt er nicht dar, inwiefern die vollumfängliche Aufhebung des angefochtenen Entscheids des TAS vom 29. Juni 2011 begründet sein sollte (vgl. <ref-ruling> E. 3 S. 606). In Ziffer 1 wird das Rechtsmittel des Real Saragossa SAD abgewiesen. Gegen diese Dispositiv-Ziffer ist der Beschwerde keine Begründung zu entnehmen. Auf die Beschwerde ist nicht einzutreten, soweit sie sich gegen Dispositiv-Ziffer 1 des angefochtenen Entscheids richtet.
3. Der Beschwerdeführer rügt eine Verletzung des rechtlichen Gehörs (<ref-law>).
Er rügt ausschliesslich eine Verletzung seines Gehörsanspruchs im Verfahren vor der FIFA-Disziplinarkommission; dass er im Schiedsverfahren vor dem TAS nicht die Möglichkeit gehabt hätte, sich ins Verfahren einzubringen, bringt er hingegen nicht vor. Seine Argumentation, nach der eine Heilung der im Rahmen des verbandsinternen Disziplinarverfahrens angeblich ungenügenden Anhörung durch das Schiedsverfahren vor dem TAS - entgegen dem angefochtenen Entscheid - trotz der umfassenden Prüfungsbefugnis des TAS (vgl. R57 Abs. 1 TAS Code) nicht in Frage kommen soll, überzeugt nicht. Entgegen dem, was der Beschwerdeführer anzunehmen scheint, ergibt sich aus dem Grundsatz des rechtlichen Gehörs (<ref-law>) kein Anspruch auf einen doppelten Instanzenzug bzw. ein zweistufiges Schiedsverfahren (vgl. Urteile 4A_530/2011 vom 3. Oktober 2011 E. 3.3.2; 4A_386/2010 vom 3. Januar 2011 E. 6.2 mit Hinweis).
4. Der Beschwerdeführer rügt eine Verletzung des Ordre public im Sinne von <ref-law>.
4.1 Der Ordre public (<ref-law>) hat sowohl einen materiellen als auch einen verfahrensrechtlichen Gehalt (<ref-ruling> E. 2.2.1 S. 392; <ref-ruling> E. 4a S. 194; <ref-ruling> E. 3b S. 253 mit Hinweisen). 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 und der Schutz von Handlungsunfähigen (<ref-ruling> E. 2.2.1; <ref-ruling> E. 6b S. 198 mit Hinweis).
Diese Aufzählung ist jedoch nicht abschliessend (Urteil 4A_458/2009 vom 10. Juni 2010 E. 4.1, in: SJ 2010 I S. 417). Auch die Versprechen von Schmiergeldzahlungen verstossen gegen den Ordre public, sofern sie nachgewiesen sind (<ref-ruling> E. 4b S. 384 f.; Urteil 4P.208/2004 vom 14. Dezember 2004 E. 6.1). Im Weiteren hat das Bundesgericht erwogen, dass ein Entscheid, der - auch nur mittelbar - einen derart fundamentalen Rechtsgrundsatz wie das Verbot der Zwangsarbeit missachtet, gegen den materiellen Ordre public verstösst (Urteil 4A_370/2007 vom 21. Februar 2008 E. 5.3.2). Ein Verstoss gegen den Ordre public ist sodann bei einer Verletzung von <ref-law> denkbar (vgl. Urteile 4A_458/2009 vom 10. Juni 2010 E. 4.4.3.2, in: SJ 2010 I S. 417; 4A_320/2009 vom 2. Juni 2010 E. 4.4; 4P.12/2000 vom 14. Juni 2000 E. 5b/aa mit Hinweisen). Der angefochtene Schiedsentscheid wird im Übrigen nur aufgehoben, wenn er nicht allein in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 6a S. 167).
4.2 Der Beschwerdeführer bringt vor, da er seinem früheren Arbeitgeber FC Shakhtar Donetsk den Schadenersatz von EUR 11'858'934.-- nebst Zins zu 5 % seit dem 5. Juli 2007 nicht zahlen könne, werde ihm als professionellem Fussballspieler faktisch ein unbefristetes und weltweites Berufsverbot auferlegt, sofern der Gläubiger dies verlange. Er sieht darin einen schwerwiegenden Verstoss gegen die in Art. 27 Abs. 2 der Bundesverfassung (BV) und in internationalen Konventionen garantierte Berufsfreiheit sowie eine übermässige Beschränkung der persönlichen Freiheit, wie sie in Art. 27 des schweizerischen Zivilgesetzbuchs (ZGB) konkretisiert ist.
Entgegen der im angefochtenen Schiedsentscheid vertretenen Ansicht hat das Bundesgericht die Frage, ob es sich bei den verhängten bzw. angedrohten Disziplinarmassnahmen um eine schwere Persönlichkeitsverletzung handelt, die gegebenenfalls zur Ordre public-Widrigkeit des angefochtenen Entscheids führt, mit seinem Urteil vom 2. Juni 2010 nicht vorweggenommen. Das Bundesgericht erwog lediglich, dass die fünfjährige arbeitsvertragliche Bindung des Beschwerdeführers unter dem Gesichtswinkel des Persönlichkeitsschutzes nicht unzulässig sei und sich eine übermässige Bindung auch nicht damit begründen lasse, dass der Beschwerdeführer infolge Vertragsverletzung für den eingetretenen Schaden aufzukommen habe (Urteil 4A_320/2009 vom 2. Juni 2010 E. 4.4). Zur Vereinbarkeit von vereinsrechtlichen Disziplinarmassnahmen im Falle des Ausbleibens der Schadenersatzzahlung mit dem Ordre public äussert sich der erwähnte Entscheid nicht (vgl. zudem den vergleichbaren Fall eines vertraglichen Schadenersatzanspruchs in Urteil 4A_458/2009 vom 10. Juni 2010 E. 4.4.8, in: SJ 2010 I S. 417, in dem das Bundesgericht die Frage der Ordre public-Widrigkeit einer Sanktion durch das zuständige FIFA-Organ infolge Ausbleibens der Zahlung ausdrücklich offengelassen hat).
Entgegen der im angefochtenen Schiedsentscheid vertretenen Ansicht hat das Bundesgericht die Frage, ob es sich bei den verhängten bzw. angedrohten Disziplinarmassnahmen um eine schwere Persönlichkeitsverletzung handelt, die gegebenenfalls zur Ordre public-Widrigkeit des angefochtenen Entscheids führt, mit seinem Urteil vom 2. Juni 2010 nicht vorweggenommen. Das Bundesgericht erwog lediglich, dass die fünfjährige arbeitsvertragliche Bindung des Beschwerdeführers unter dem Gesichtswinkel des Persönlichkeitsschutzes nicht unzulässig sei und sich eine übermässige Bindung auch nicht damit begründen lasse, dass der Beschwerdeführer infolge Vertragsverletzung für den eingetretenen Schaden aufzukommen habe (Urteil 4A_320/2009 vom 2. Juni 2010 E. 4.4). Zur Vereinbarkeit von vereinsrechtlichen Disziplinarmassnahmen im Falle des Ausbleibens der Schadenersatzzahlung mit dem Ordre public äussert sich der erwähnte Entscheid nicht (vgl. zudem den vergleichbaren Fall eines vertraglichen Schadenersatzanspruchs in Urteil 4A_458/2009 vom 10. Juni 2010 E. 4.4.8, in: SJ 2010 I S. 417, in dem das Bundesgericht die Frage der Ordre public-Widrigkeit einer Sanktion durch das zuständige FIFA-Organ infolge Ausbleibens der Zahlung ausdrücklich offengelassen hat).
4.3 4.3.1 Die Persönlichkeit des Menschen bedarf als fundamentales Rechtsgut des Schutzes der Rechtsordnung. Sie wird in der Schweiz etwa verfassungsrechtlich durch die Grundgarantie des Rechts auf persönliche Freiheit (<ref-law>) geschützt, die neben dem Recht auf körperliche und geistige Unversehrtheit sowie der Bewegungsfreiheit all jene Freiheiten verbrieft, die elementare Erscheinungsformen der Persönlichkeitsentfaltung darstellen (<ref-ruling> E. 2.3.1 S. 211; <ref-ruling> E. 5.2 119; je mit Hinweisen). Die freie persönliche Entfaltung wird unter anderem auch durch das Grundrecht der Wirtschaftsfreiheit gewährleistet, das insbesondere die freie Wahl des Berufes sowie den freien Zugang zu einer privatwirtschaftlichen Erwerbstätigkeit und deren freie Ausübung umfasst (<ref-law>; vgl. <ref-ruling> E. 5.1 S. 12; <ref-ruling> E. 4c/aa S. 29).
Ein Schutz der freien persönlichen Entfaltung besteht jedoch nicht nur gegenüber Beeinträchtigungen von Seiten des Staates, sondern auch gegenüber Eingriffen Privater (vgl. Art. 27 f. ZGB, die in der Schweiz die persönliche Freiheit im Privatrecht konkretisieren). Dabei ist allgemein anerkannt, dass sich eine Person durch rechtsgeschäftliche Bindung nicht gänzlich ihrer Freiheit entäussern kann und einer Beschränkung ihrer Freiheit Grenzen gesetzt sind. Der in <ref-law> niedergelegte Rechtsgrundsatz gehört zur wesentlichen, weitgehend anerkannten Wertordnung, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte.
4.3.2 Eine vertragliche Beschränkung der wirtschaftlichen Freiheit wird nach schweizerischem Verständnis als übermässig im Sinne von <ref-law> betrachtet, wenn sie den Verpflichteten der Willkür eines anderen ausliefert, seine wirtschaftliche Freiheit aufhebt oder in einem Masse einschränkt, dass die Grundlagen seiner wirtschaftlichen Existenz gefährdet sind (<ref-ruling> E. 5 S. 345 f. mit Hinweisen; vgl. auch Urteil 4P.167/1997 vom 25. November 1997 E. 2a). Auch wenn der Ordre public mit der blossen Rechtswidrigkeit nicht gleichzusetzen ist (BERNARD DUTOIT, Droit international privé suisse, 4. Aufl. 2005, N. 8 zu <ref-law> S. 678) und seine Verletzung wesentlich eingeschränkter zu würdigen ist als ein Verstoss gegen das Willkürverbot (<ref-ruling> E. 2.2.2 S. 393), kann eine derart übermässige Bindung Ordre public-widrig sein, wenn sie eine offensichtliche und schwerwiegende Persönlichkeitsverletzung darstellt (vgl. Urteile 4A_458/2009 vom 10. Juni 2010 E. 4.4.3.2, in: SJ 2010 I S. 417; 4A_320/2009 vom 2. Juni 2010 E. 4.4; 4P.12/2000 vom 14. Juni 2000 E. 5b/aa mit Hinweisen; vgl. auch EUGEN BUCHER, Berner Kommentar, 3. Aufl. 1993, N. 26 zu <ref-law>; WALTER/BOSCH/BRÖNNIMANN, Internationale Schiedsgerichtsbarkeit in der Schweiz, 1991, S. 236; ANTON HEINI, in: Zürcher Kommentar zum IPRG, 2. Aufl. 2004, N. 45 zu <ref-law>; WOLFGANG PORTMANN, Einseitige Optionsklauseln in Arbeitsverträgen von Fussballspielern, Causa Sport 2006 S. 209).
4.3.3 Die Schranken rechtsgeschäftlicher Bindung aufgrund des Persönlichkeitsschutzes gelten nicht nur für vertragliche Vereinbarungen, sondern auch für Statuten und Beschlüsse von Körperschaften (BUCHER, a.a.O., N. 18 zu <ref-law>; vgl. bereits <ref-ruling> E. 2 S. 8 f.). Vereinsstrafen, welche nicht bloss den korrekten Ablauf der Spiele sichern, sondern eigentlich in die rechtlichen Interessen der Betroffenen eingreifen, werden nach der Rechtsprechung der gerichtlichen Kontrolle unterworfen (<ref-ruling> E. 2 S. 370; <ref-ruling> E. 3c; <ref-ruling> E. 2 S. 15 ff.; vgl. schon <ref-ruling> E. 3 S. 19 ff.). Dies gilt insbesondere, wenn Vereinsstrafen das Persönlichkeitsrecht auf wirtschaftliche Entfaltung schwerwiegend beeinträchtigen; für diesen Fall hat das Bundesgericht erkannt, dass die Ausschlussautonomie eines Vereins durch das Persönlichkeitsrecht seiner Mitglieder beschränkt ist, wenn er als massgebende Organisation des betreffenden Berufsstandes oder Wirtschaftszweiges in der Öffentlichkeit auftritt (<ref-ruling> E. 2c/bb und cc S. 197 ff.). Dies entspricht dem Standpunkt, der insbesondere für Sportvereine eingenommen worden ist (<ref-ruling> E. 2c/bb S. 198 mit Hinweisen; vgl. auch <ref-ruling> E. 4.5 S. 200). In diesen Fällen wird das Recht des Vereins auf Ausschliessung seines Mitglieds nicht nur unter dem Gesichtspunkt des Rechtsmissbrauchs überprüft, sondern es wird unter Berücksichtigung des Eingriffs in die Persönlichkeit eine Interessenabwägung vorgenommen und abgeklärt, ob ein wichtiger Grund vorliegt (<ref-ruling> E. 2c/cc S. 198 f.; vgl. auch <ref-ruling> E. 4.4).
Diese Grundsätze gelten auch für nach dem schweizerischen Recht verfasste Vereine mit Sitz in der Schweiz, die - wie die FIFA - den internationalen Sport ordnen. Massnahmen solcher Sportverbände, welche die wirtschaftliche Entfaltung der natürlichen Personen schwerwiegend beeinträchtigen, die den Sport als Beruf betreiben, sind nur zulässig, wenn das Gewicht der Verbandsinteressen den Eingriff in die Persönlichkeit überwiegt.
4.3.4 Der Beschwerdeführer hat als professioneller Fussballspieler seine arbeitsvertraglichen Pflichten gegenüber dem ukrainischen Verein FC Shakhtar Donetsk verletzt und ist aus diesem Grund zu Schadenersatz verurteilt worden - in solidarischer Haftung mit dem Fussballclub, der ihn während der noch laufenden Vertragsdauer angestellt hatte (vgl. Urteil 4A_320/2009 vom 2. Juni 2010). Die umstrittene Vereinsstrafe, die das TAS auf eine rechtsgeschäftliche Bindung des Beschwerdeführers an die in Art. 64 FIFA-Disziplinarreglement niedergelegten Sanktionen stützt, dient der privaten Vollstreckung des Urteils auf Schadenersatz, nachdem die Forderung nicht bezahlt worden ist. Der Beschwerdeführer soll auf einfache Aufforderung des Gläubigers mit einer Berufssperre für alle mit Fussball zusammenhängenden Tätigkeiten belegt werden, bis die Forderung von mehr als EUR 11 Mio., nebst 5 % Zins seit Mitte 2007 (d.h. EUR 550'000.-- jährlich), bezahlt ist. Es soll damit unmittelbar das Interesse eines Mitglieds der FIFA an der Bezahlung der Schadenersatzforderung durch den vertragsbrüchigen Arbeitnehmer und mittelbar das Interesse des Sportverbands an der Vertragstreue der Fussballspieler durchgesetzt werden.
Der Eingriff in die wirtschaftliche Freiheit des Beschwerdeführers mag geeignet sein, die Bereitschaft zur Zahlung und Bemühungen zur Aufbringung des geschuldeten Betrags zu fördern; wenn allerdings die Behauptung des Beschwerdeführers zutrifft, dass er jedenfalls den ganzen Betrag nicht zahlen kann, ist schon die Eignung der Massnahme zur Erreichung des unmittelbaren Zieles - nämlich der Bezahlung der Schadenersatzforderung - fraglich. Denn mit dem Verbot der bisher ausgeübten wirtschaftlichen und verwandter Tätigkeiten wird dem Beschwerdeführer die Möglichkeit genommen, durch Betätigung in seinem angestammten Beruf ein Einkommen zu erzielen, um seiner Verpflichtung nachzukommen. Die Vereinsstrafe ist aber jedenfalls zur Durchsetzung der verfügten Schadenersatzforderung nicht erforderlich: Dem ehemaligen Arbeitgeber des Beschwerdeführers steht die Vollstreckung des Urteils des TAS vom 19. Mai 2009 auf dem Weg des New Yorker Übereinkommens vom 10. Juni 1958 über die Anerkennung und Vollstreckung ausländischer Schiedssprüche (SR 0.277.12) offen, dem die meisten Staaten beigetreten sind und das insbesondere auch für den aktuellen Wohnsitzstaat des Beschwerdeführers Italien gilt.
Die Vereinsstrafe ist aber insbesondere auch insoweit unzulässig, als die Interessen, welche der Weltfussballverband damit durchsetzen will, den schwerwiegenden Eingriff in die Persönlichkeit des Beschwerdeführers nicht zu rechtfertigen vermögen. Das abstrakte Ziel der Durchsetzung der Vertragstreue der Fussballspieler gegenüber ihren Arbeitgebern ist eindeutig weniger gewichtig als das faktisch in zeitlicher und örtlicher Hinsicht unbegrenzte Berufsverbot des Beschwerdeführers für alle im Zusammenhang mit dem Fussballsport stehenden Betätigungen.
4.3.5 Die auf Art. 64 Abs. 4 des FIFA-Disziplinarreglements gestützte Androhung eines unbegrenzten Berufsverbots stellt einen offensichtlichen und schwerwiegenden Eingriff in die Persönlichkeitsrechte des Beschwerdeführers dar und missachtet die in <ref-law> verankerten grundlegenden Schranken rechtsgeschäftlicher Bindung. Der angefochtene Schiedsentscheid führt bei Ausbleiben der auferlegten Zahlung nicht nur dazu, dass der Beschwerdeführer der Willkür seines ehemaligen Arbeitgebers ausgesetzt, sondern insbesondere seine wirtschaftliche Freiheit in einem Masse eingeschränkt wird, dass die Grundlagen seiner wirtschaftlichen Existenz gefährdet sind, ohne dass dies durch ein überwiegendes Interesse des Weltfussballverbands bzw. seiner Mitglieder gerechtfertigt wäre. Aufgrund der entsprechenden Androhung stellt der Schiedsentscheid des TAS vom 29. Juni 2011 eine offensichtliche und schwerwiegende Persönlichkeitsverletzung dar und ist mit dem Ordre public (<ref-law>) unvereinbar.
5. Dispositiv-Ziffern 2 - 6 des Schiedsentscheids des TAS vom 29. Juni 2011 sind in Gutheissung der Beschwerde aufzuheben, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und Dispositiv-Ziffern 2 - 6 des Schiedsentscheids des TAS vom 29. Juni 2011 werden aufgehoben.
2. Die Gerichtskosten von Fr. 25'000.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 30'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 27. März 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann