Sachverhalt: A. A.a. X._ (Beschwerdeführer) mit Wohnsitz in M._, Ukraine, ist der Sportdirektor des FC Metalist, einem Fussballclub in Kharkiv. Er war in dieser Funktion bereits während der Saison 2007/2008 der ukrainischen Meisterschaft tätig. 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, ein Fussballclub aus Lviv, in der 26. Meisterschaftsrunde gegen den FC Metalist, 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 erfahrener Spieler des FC Karpaty, 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. B. B.a. Mit Entscheid vom 9. August 2010 sprach die Kontroll- und Disziplinarkommission des ukrainischen Fussballverbands (FFU Control and Disciplinary Committee) Bussen und weitere Sanktionen gegen verschiedene Spieler, Funktionäre und den FC Metalist aus. Gegen X._ wurde ein lebenslängliches Verbot ausgesprochen, fussballbezogene Aktivitäten auszuüben. Die Kommission sah es aufgrund der Zeugenaussagen und der vorgelegten Beweismittel als erwiesen an, dass das Fussballspiel vom 19. April 2008 manipuliert worden war. B.b. Auf Berufung hin wurde die gegen X._ verhängte Sperre mit Entscheid der Berufungskommission des ukrainischen Fussballverbands (FFU Appeal Committee) vom 19. Oktober 2010 auf fünf Jahre herabgesetzt; zudem wurde ihm eine Busse von USD 10'000.--, zahlbar in ukrainischen Hrywnja, auferlegt. B.c. Mit Schiedsentscheid vom 2. August 2013 wies das Tribunal Arbitral du Sport (TAS) eine von X._ gegen den Entscheid der Berufungskommission vom 19. Oktober 2010 erhobene Berufung ab und bestätigte den angefochtenen Entscheid. Das TAS ging davon aus, dass das Lviv-Video ohne Zustimmung von A._ aufgenommen wurde, weshalb es unter anderem dessen Verwertbarkeit prüfte. Das Schiedsgericht erachtete das Lviv-Video gestützt auf eine Abwägung der betroffenen Interessen für verwertbar, während es die Abschrift eines rechtswidrig auf Tonband aufgenommenen Telefongesprächs mit einem der beteiligten Fussballspieler für unverwertbar erklärte und eine weitere Videoaufnahme nur deshalb als Beweis zuliess, weil sich X._ und weitere Appellanten zu ihrer Entlastung selber darauf beriefen. Das TAS sah es aufgrund des Lviv-Videos sowie weiterer Indizien für erwiesen an, dass X._ für die Manipulation des Spiels vom 19. April 2008 Geld angeboten und bezahlt hatte, womit er die massgebenden Verbandsregeln verletzte. C. Mit Beschwerde in Zivilsachen beantragt X._ dem Bundesgericht, der Schiedsentscheid des TAS vom 2. August 2013 sei, soweit er ihn betreffe, aufzuheben. Sowohl die Beschwerdegegnerin als auch das TAS haben auf Vernehmlassungen zur Beschwerde verzichtet. D. Mit Verfügung vom 15. August 2013 wies das Bundesgericht das Gesuch des Beschwerdeführers um superprovisorische Erteilung der aufschiebenden Wirkung ab. Nachdem die Beschwerdegegnerin mit Eingaben vom 15. und 16. August 2013 ihre Zustimmung erklärt hatte, erteilte das Bundesgericht der Beschwerde mit Verfügung vom 16. August 2013 die aufschiebende Wirkung.