Citation: 4A_448/2013 E. A

A.a. A.________ (Beschwerdeführer) mit Wohnsitz in N.________, Ukraine, spielte während der Saison 2007/2008 im Rahmen der ukrainischen Meisterschaft für den FC Karpaty, einem Fussballclub in Lviv. The Football Federation of Ukraine (FFU; Beschwerdegegnerin) ist der nationale Fussballverband der Ukraine und als solcher Mitglied der Fédération Internationale de Football Association (FIFA) und der Union des Associations Européennes de Football (UEFA). A.b. Am 19. April 2008 spielte der FC Karpaty in der 26. Meisterschaftsrunde gegen den FC Metalist, einem Fussballclub in Kharkiv, der zu diesem Zeitpunkt den dritten Tabellenplatz belegte. Das Spiel wurde in Kharkiv ausgetragen und endete 4:0 für den FC Metalist. Während des Spiels schoss A.________ ein Eigentor und erhielt zudem die rote Karte. Am 21. April 2008 traf der Präsident der FFU, B.________, in einem Restaurant in Lviv C.________, den Ehrenpräsidenten des FC Karpaty, um die Organisation der Europameisterschaft 2012 zu besprechen. Unter anderem kamen dabei das Spiel vom 19. April 2008 und Gerüchte zur Sprache, der Spielverlust sei von den Spielern des FC Karpaty absichtlich herbeigeführt worden. Kurz nach diesem Treffen leitete C.________ beim FC Karpaty eine interne Untersuchung ein, um zu klären, ob das Spiel tatsächlich manipuliert wurde. Am 15. Mai 2008 führte C.________ in seinem Haus ein Gespräch mit A.________ hinsichtlich der Hintergründe des Spiels vom 19. April 2008. Am folgenden Tag traf er ihn nochmals in Lviv; diesmal im Büro von C.________, wobei das Gespräch auf Video aufgenommen wurde (nachfolgend als Lviv-Video bezeichnet). Dabei teilte ihm A.________ mit, dass ihn X.________ vom Club FC Metalist, mit dem er bekannt war, am Vorabend des Spiels angerufen habe. X.________ habe ihm für den Spielverlust Geld angeboten, wobei er erwähnt habe, die Schiedsrichter würden den FC Karpaty sonst ohnehin "erledigen". X.________ habe ihm vorgeschlagen, das Angebot mit dem Mannschaftskapitän zu besprechen. A.________ sagte weiter aus, er habe daraufhin mit dem damaligen Spielführer, D.________, und der Kernmannschaft gesprochen; sie seien sich einig gewesen, das Geld anzunehmen. Er habe zusammen mit den erfahreneren Spielern D.________, E.________ und F.________ alle weiteren Mitglieder der Mannschaft einzeln angerufen, um das Angebot zu besprechen. A.________ führte weiter aus, es seien ihm bei seiner Hotelunterkunft von einem Fahrzeug aus insgesamt USD 110'000.-- ausgehändigt worden. Sämtliche Mannschaftsmitglieder - auch die Austauschspieler - hätten Geld erhalten. Er selbst habe mit dem Mannschaftskapitän D.________ das Geld unter die einzelnen Spieler aufgeteilt, die es bei ihm auf dem Hotelzimmer in Anwesenheit von D.________, E.________ und G.________ abholten. Jeder der ursprünglich aufgestellten Spieler habe USD 10'000.-- erhalten, wobei den jüngeren Spielern jeweils USD 1'000.-- zugunsten der Austauschspieler abgezogen worden seien. Am 30. Mai 2008 beendeten A.________ und der FC Karpaty das Arbeitsverhältnis durch gegenseitige Übereinkunft auf den 31. Mai 2008 per Saldo aller Ansprüche. Daraufhin wurde A.________ zum ukrainischen Club FC Shakhtar transferiert.