Sachverhalt:
A. A.a X._, Tschechische Republik, (Beschwerdeführer) investiert unter anderem in grosse Unternehmen der tschechischen Stahl- und Maschinenindustrie.
Die AY._ Holding B.V. (vormals AAY._ Group Holding B.V.) (Beschwerdegegnerin) ist eine niederländische Holdinggesellschaft, die unter anderem an zahlreichen tschechischen Unternehmen beteiligt ist. Die Beschwerdegegnerin wird von Y._, Tschechische Republik, beherrscht.
A.b Am 9. November 2005 schloss der Beschwerdeführer mit Y._ einen "Vertrag über Gemeinsames Vorgehen" ab. Mit Kaufvertrag vom gleichen Tag mit der Beschwerdegegnerin verpflichtete sich der Beschwerdeführer, seinen Aktienanteil von 45 % der Gesellschaft A._ Holding an die Beschwerdegegnerin zu übertragen. Dem Beschwerdeführer sollte durch Zeichnung der anlässlich einer Kapitalerhöhung neu ausgegebenen Aktien der Beschwerdegegnerin sowie unter Verrechnung der Liberierungsforderung mit dem Kaufpreisanspruch des Beschwerdeführers eine 50 %-Beteiligung an der Beschwerdegegnerin verschafft werden. Der "Vertrag über Gemeinsames Vorgehen" sah für den Fall der Nichterfüllung bestimmter Vertragspflichten eine Konventionalstrafe vor. Beide Verträge enthalten zudem eine Rechtswahlklausel zugunsten des tschechischen Rechts sowie eine Schiedsklausel.
Die Kapitalerhöhung kam in der Folge nicht zustande und die Übertragung der Aktien der Gesellschaft A._ Holding blieb ebenfalls aus.
B. B.a Die Beschwerdegegnerin erhob mit Eingabe vom 9. November 2006 bei der Internationalen Handelskammer (ICC) Schiedsklage gegen den Beschwerdeführer und verlangte gestützt auf den Aktienkaufvertrag vom 9. November 2005 die Übertragung der von ihm gehaltenen Aktien der A._ Holding (Verfahren ICC Nr. _).
Der Beschwerdeführer erhob seinerseits gestützt auf den "Vertrag über Gemeinsames Vorgehen" vom 9. November 2005 Schiedsklage gegen Y._ auf Zahlung der Konventionalstrafe (Verfahren ICC Nr. _). Dieser verlangte widerklageweise ebenfalls die Zahlung der Konventionalstrafe.
Die beiden Verfahren wurden von denselben Schiedsrichtern beurteilt. Der Beschwerdeführer nominierte jeweils Q._, die Beschwerdegegnerin bzw. Y._ nominierten P._ als Schiedsrichter; diese einigten sich auf O._ als Obmann. Auf eine Vereinigung der beiden Verfahren verzichtete das Schiedsgericht.
B.b Mit Entscheid vom 15. Mai 2009 hiess das Schiedsgericht im Verfahren ICC Nr. _ die Klage der Beschwerdegegnerin gut und verurteilte den Beschwerdeführer zur Übertragung der Aktien der A._ Holding gegen Entrichtung eines Kaufpreises von CZK 1'182'500'000.-- (entsprechend knapp Fr. 67 Mio.). Das Schiedsgericht erwog dabei unter anderem, dass der Aktienkaufvertrag vom 9. November 2005 unabhängig von der Wirksamkeit des "Vertrags über Gemeinsames Vorgehen" zu erfüllen sei.
C. Mit (innert Frist ergänzter) Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Schiedsentscheid vom 15. Mai 2009 in der Schiedssache ICC Nr. _ aufzuheben.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Der Obmann des Schiedsgerichts hat sich in zwei Eingaben geäussert und beantragt sinngemäss ebenfalls die Abweisung der Beschwerde, soweit darauf eingetreten werden könne.
Der Beschwerdeführer reichte dem Bundesgericht eine Replik, die Beschwerdegegnerin eine Duplik ein. Der Beschwerdeführer nahm in einer weiteren Eingabe zur Duplik Stellung; die Beschwerdegegnerin wiederum äusserte sich dazu in einer kurzen Eingabe. Die Beschwerdegegnerin reichte dem Bundesgericht sodann ein "Gesuch um Beschleunigung des Verfahrens" ein.
D. Mit Verfügung des Bundesgerichts vom 24. Juli 2009 wurde der Beschwerde die aufschiebende Wirkung zuerkannt und der Eventualantrag der Beschwerdegegnerin um Sicherstellung des Betrags von Fr. 1'128'352.-- abgewiesen.

Erwägungen:
1. 1.1 Das von der Beschwerdegegnerin eingereichte "Gesuch um Beschleunigung des Verfahrens" wird mit dem Entscheid in der Sache gegenstandslos.
1.2 Der Beschwerdeführer beantragt, es sei das vorliegende Verfahren aufgrund der Identität der Rüge der vorschriftswidrigen Zusammensetzung des Schiedsgerichts mit dem Beschwerdeverfahren 4A_258/2009 zu vereinigen. Grundsätzlich besteht die Möglichkeit der Vereinigung verschiedener bundesgerichtlicher Verfahren (vgl. <ref-ruling> E. 1a S. 385; <ref-ruling> E. 1 S. 272). Die beiden vom Beschwerdeführer erhobenen Beschwerden richten sich jedoch gegen Entscheide, die im Rahmen zweier Schiedsverfahren ergangen sind, in denen der Beschwerdeführer jeweils verschiedenen Parteien gegenüberstand und unterschiedliche Ansprüche zu beurteilen waren. Zwar erhebt er in beiden Verfahren aufgrund der identischen Zusammensetzung der Schiedsgerichte im Wesentlichen die gleiche Rüge der fehlenden Unabhängigkeit zweier Schiedsrichter (<ref-law>), den übrigen Rügen liegen aber unterschiedliche tatsächliche und rechtliche Verhältnisse zugrunde. Eine Vereinigung der beiden Verfahren drängt sich vorliegend nicht auf.
2. Die Beschwerde in Zivilsachen ist gegen Entscheide von Schiedsgerichten unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Parteien haben ihren Sitz nicht in der Schweiz. Da sie 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 Beschwerdegegnerin macht zu Unrecht geltend, auf die Beschwerde könne nicht eingetreten werden, weil die Parteien in der Schiedsvereinbarung auf die Erhebung von Rechtsmitteln gegen den Schiedsentscheid verzichtet hätten.
Hat keine der Parteien Wohnsitz, gewöhnlichen Aufenthalt oder eine Niederlassung in der Schweiz, wie dies vorliegend der Fall ist, so können sie zwar nach <ref-law> die Anfechtung der Schiedsentscheide durch eine ausdrückliche Erklärung in der Schiedsvereinbarung oder in einer späteren Übereinkunft vollständig ausschliessen. Nach der Rechtsprechung des Bundesgerichts muss aus der Erklärung jedoch der gemeinsame Wille der Parteien unmissverständlich hervorgehen, von der Möglichkeit im Sinne von <ref-law> Gebrauch zu machen und auf die Anfechtung des internationalen Schiedsentscheids beim Bundesgericht zu verzichten. Ob es sich so verhält, ist durch Auslegung der konkreten Schiedsklausel zu ermitteln (vgl. <ref-ruling> E. 4.3.1 S. 240 f.; <ref-ruling> E. 4.2, insb. E. 4.2.3.1 S. 177 ff.; je mit Hinweisen).
Nach dem Wortlaut der zu beurteilenden Schiedsklausel werden Streitigkeiten aus dem Vertrag "unter Ausschluss der Zuständigkeit der allgemeinen Gerichte und endgültig gemäss den Regeln des Schiedsgerichts der Internationalen Handelskammer" entschieden. Dies genügt entgegen der Ansicht der Beschwerdegegnerin den Anforderungen an einen ausdrücklichen Verzicht im Sinne von <ref-law> nicht. Zum einen wird mit dem Hinweis auf den Ausschluss der Zuständigkeit der "allgemeinen Gerichte" lediglich zum Ausdruck gebracht, dass ein Schiedsgericht anstelle der staatlichen Gerichte über allfällige Streitigkeiten entscheiden soll. Ein Wille der Vertragsparteien, auf die Anfechtung des Schiedsentscheids beim Bundesgericht zu verzichten, lässt sich daraus nicht ableiten. Zum anderen schliesst die Bezeichnung eines Entscheids als "endgültig" nach allgemeinem Sprachgebrauch im Zivilprozessrecht einen Weiterzug mit ausserordentlichen Rechtsmitteln nicht aus, sondern lediglich die (freie) Prüfung des Entscheids mittels ordentlicher Rechtsmittel, wie beispielsweise einer Berufung (vgl. die Urteile 4A_224/2008 vom 10. Oktober 2008 E. 2.6.3; 4P.114/2006 vom 7. September 2006 E. 5.3; je mit Hinweisen). So bestimmt denn auch <ref-law> in Absatz 1, dass der Entscheid des Schiedsgerichts "endgültig" sei, sieht aber in den folgenden beiden Absätzen 2 und 3 in Verbindung mit <ref-law> eine Anfechtungsmöglichkeit aus abschliessend aufgezählten Gründen beim Bundesgericht als einziger Beschwerdeinstanz mit dem Rechtsmittel der Beschwerde in Zivilsachen nach <ref-law> vor.
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). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
2.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von Art. 97 sowie Art. 105 Abs. 2 BGG ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 5 S. 141; <ref-ruling> E. 5.2.2 S. 733; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
3. Der Beschwerdeführer rügt unter Berufung auf <ref-law>, das Schiedsgericht sei vorschriftswidrig zusammengesetzt gewesen. Er bringt vor, der von der Beschwerdegegnerin nominierte P._ sowie der Vorsitzende des Schiedsgerichts, O._, seien befangen gewesen, weshalb keine Gewähr für ein unparteiliches und unabhängiges Schiedsgericht bestanden habe.
3. Der Beschwerdeführer rügt unter Berufung auf <ref-law>, das Schiedsgericht sei vorschriftswidrig zusammengesetzt gewesen. Er bringt vor, der von der Beschwerdegegnerin nominierte P._ sowie der Vorsitzende des Schiedsgerichts, O._, seien befangen gewesen, weshalb keine Gewähr für ein unparteiliches und unabhängiges Schiedsgericht bestanden habe.
3.1 3.1.1 Der Beschwerdeführer habe Ende Mai 2007 aus den tschechischen Medien erfahren, dass die ICC P._ in einem anderen Schiedsverfahren (gegen Z._), bei dem dieser ebenfalls von der Beschwerdegegnerin nominiert worden sei, nicht bestätigt habe, weil er zu häufig von Y._ oder von mit diesem verbundenen Personen nominiert worden sei. Im genannten Zeitungsartikel sei "davon die Rede, dass JUDr. P._ von Y._ bzw. von mit ihm verbundenen Personen in letzter Zeit in ca. 10 verschiedenen Schiedsverfahren als Schiedsrichter nominiert worden sei". Dies könne der Beschwerdeführer aus eigener Anschauung bestätigen, da er Y._ im Jahr 2006 auch in zwei Verfahren vor dem Schiedsgericht bei der Wirtschaftskammer der Tschechischen Republik gegenübergestanden sei. Auch dort habe P._ als ernannter Parteischiedsrichter auf Seiten von Y._ gestanden und sei daher im Laufe der Zeit zu dessen "Hausschiedsrichter" geworden. Dennoch habe die ICC P._ im vorliegenden Schiedsverfahren am 27. April 2007 bestätigt und auch den Ablehnungsantrag des Beschwerdeführers mit Entscheid vom 28. September 2007, wie üblich ohne Begründung, abgewiesen.
3.1.2 Gegen einen Ablehnungsentscheid eines privaten Gremiums wie dem Internationalen Schiedsgerichtshof der ICC ist ein direkter Rechtsbehelf ausgeschlossen; ein solcher Entscheid ist jedoch einer indirekten Überprüfung im Rahmen eines Beschwerdeverfahrens gegen den Schiedsspruch selbst zugänglich (<ref-ruling> E. 2.2 S. 332; <ref-ruling> E. 3b S. 360 f.). Der Beschwerdeführer zeigt allerdings, soweit seine Vorbringen überhaupt genügend substantiiert sind, keine Umstände auf, die Anlass zu berechtigten Zweifeln an der Unabhängigkeit von P._ (vgl. <ref-law>) geben würden.
Zunächst ist die einzig gestützt auf einen Zeitungsartikel vom 20. Mai 2007 erhobene Behauptung, P._ sei "in letzter Zeit" in zahlreichen Fällen von Y._ bzw. "von mit diesem verbundenen Personen" als Schiedsrichter nominiert worden, zu unbestimmt, als dass deren Wahrheitsgehalt anhand eines Beweisverfahrens geklärt und gestützt darauf die Unabhängigkeit des fraglichen Schiedsrichters beurteilt werden könnte. Der Beschwerdeführer hätte zumindest die verschiedenen Schiedsverfahren unter Angabe der zeitlichen Abfolge sowie der daran beteiligten Schiedsparteien konkret benennen und aufzeigen müssen, welche Partei P._ ernannt hat und in welcher Beziehung diese zur Beschwerdegegnerin steht. Der blosse Umstand, dass P._ in einem anderen ICC Schiedsverfahren zwischen der Beschwerdegegnerin und einem Herrn Z._ (ICC Nr. _) vom Internationalen Schiedsgerichtshof der ICC die Bestätigung versagt wurde, lässt zudem keine Rückschlüsse auf die Frage der Unabhängigkeit im vorliegenden Verfahren zu. Entgegen der in der Beschwerde erhobenen Behauptung ergibt sich aus dem Schreiben der ICC vom 27. April 2007 in der Sache ICC Nr. _ nicht, dass die Bestätigung aufgrund einer "engen Verflechtung" mit der Beschwerdegegnerin verweigert worden wäre.
An den beiden in der Beschwerde erwähnten Verfahren vor dem Schiedsgericht bei der Wirtschaftskammer der Tschechischen Republik im Jahr 2006 war der Beschwerdeführer nach eigenen Angaben selbst als Partei beteiligt. Er hatte demnach Kenntnis davon, dass P._ in diesen Schiedsverfahren von Y._ nominiert worden war, als P._ am 27. April 2007 im vorliegenden Verfahren vom Schiedsgerichtshof der ICC als Schiedsrichter bestätigt wurde. Hätte er sich auf den Umstand berufen wollen, dass P._ in den letzten drei Jahren bereits mindestens zweimal als Schiedsrichter durch die Gegenpartei bzw. eine verbundene Person nominiert worden wäre, so hätte er dies unverzüglich nach dessen Bestätigung vorbringen müssen und mit seinem Ablehnungsbegehren nicht bis zum 17. August 2007 zuwarten dürfen (vgl. <ref-law>). Der Beschwerdeführer hat seinen Anspruch auf spätere Anrufung des Ablehnungsgrunds daher verwirkt (vgl. <ref-ruling> E. 3.1 S. 449; <ref-ruling> E. 3c S. 253 f.; je mit Hinweisen).
Es braucht unter diesen Umständen nicht darauf eingegangen zu werden, wie es sich mit dem Argument des Beschwerdeführers verhält, gemäss Ziffer 3.1.3 der Richtlinien der International Bar Association (IBA Guidelines on Conflicts of Interest in International Arbitration, genehmigt am 22. Mai 2004; «http://www.ibanet.org», unter Publications/IBA guides and free materials [besucht am 3. März 2010]) könne ein Schiedsrichter, der in den letzten drei Jahren mehr als zweimal von der gleichen Partei als Schiedsrichter ernannt wurde, nur dann amten, wenn er diese Tatsache offengelegt habe und die Parteien gegen sein Wirken keine Einwände erhoben hätten. Im Übrigen verweist der Beschwerdeführer auf Ziffer 2.3.6 der erwähnten IBA Guidelines, wonach eine bedeutende wirtschaftliche Beziehung der Anwaltskanzlei des Schiedsrichters zu einer Partei oder einer mit dieser verbundenen Person einen Interessenkonflikt darstelle und der Schiedsrichter nur amten könne, wenn die Parteien sich im Wissen um diesen Umstand ausdrücklich mit dessen Mitwirkung einverstanden erklärt hätten. Er zeigt jedoch nicht konkret auf, worin im zu beurteilenden Fall eine derartige bedeutende wirtschaftliche Beziehung bestehen soll.
Die Rüge, der von der Beschwerdegegnerin nominierte Schiedsrichter P._ sei befangen gewesen bzw. es habe der Anschein der Voreingenommenheit bestanden, geht fehl.
Die Rüge, der von der Beschwerdegegnerin nominierte Schiedsrichter P._ sei befangen gewesen bzw. es habe der Anschein der Voreingenommenheit bestanden, geht fehl.
3.2 3.2.1 Die angebliche Befangenheit des Obmanns O._ begründet der Beschwerdeführer mit Umständen, von denen er Ende Oktober 2008 anlässlich eines Schiedsverfahrens in London zwischen einer von ihm errichteten Stiftung und der Gesellschaft B._ Limited erfahren habe. So seien die Eigentümer der B._ Limited, die Herren S._ und T._, gleichzeitig Mehrheitsaktionäre und Verwaltungsräte der slowakischen Gesellschaft C._ a.s. mit Sitz in Bratislava. Der Schiedsobmann O._ sei ebenfalls im Verwaltungsrat der C._ a.s. und sitze zudem mit denselben Personen zusammen im Verwaltungsrat einer weiteren Gesellschaft, der D._ a.s. (Bratislava).
Der Beschwerdeführer bringt weiter vor, er habe weitere Nachforschungen angestellt, nachdem er über diese seltsame "Connection" misstrauisch geworden sei. Er habe dabei erfahren müssen, dass dieselbe C._ s.a. mit Y._ bzw. von diesem beherrschten Gesellschaften offenbar regelmässig zusammenarbeite. So sei die Gesellschaft in die Schaffung der Beschwerdegegnerin eingebunden gewesen, indem sie für diese Aktien der tschechischen Industriegesellschaft E._ gehalten und ihr diese im Jahr 2005 verkauft habe.
Noch enger sei die Zusammenarbeit zwischen der C._ a.s. und Y._ im Prozess um Forderungen der in den 90er-Jahren in Konkurs gefallenen Bank F._ a.s. gegenüber einer zweiten tschechischen Grossbank, G._ a.s., gewesen: So habe die C._ a.s. im März 2005 mit der niederländischen Gesellschaft H._ B.V. ein sogenanntes "Consignment Agreement" abgeschlossen, wonach die I._ a.s. in eigenem Namen, aber auf Rechnung der H._ B.V. eine Forderung in Höhe von CZK 40 Milliarden gegen die Grossbank G._ a.s. schiedsgerichtlich durchsetzen sollte. In dem in der Folge eingeleiteten Verfahren ICC Nr. _ habe P._ als Obmann geamtet. Die Anwaltskanzlei der I._ a.s. in diesem Verfahren, J._, vertrete in Tschechien regelmässig auch die Interessen von Y._ und der mit ihm verbundenen Personen. Dem Anhang eines E-Mails dieser Kanzlei vom 17. März 2006 lasse sich der Entwurf einer Vollmacht der H._ B.V. zur Geltendmachung der Forderung gegenüber der Grossbank G._ a.s. im Verfahren ICC Nr. _ entnehmen. Im E-Mail schreibe eine Frau K._ hierzu, dass man sich der C._ a.s. aus Kostengründen eventuell entledigen wolle und Y._ bzw. seine BY._ Group a.s. "es selber machen werde", womit die Geltendmachung der Forderung gemeint sei. Daraus ergebe sich, so der Beschwerdeführer, dass zwischen der C._ a.s. und Gesellschaften und Vertretern des auch die Beschwerdegegnerin beherrschenden Y._ enge wirtschaftliche Verflechtungen bestünden. Der Wortwahl des E-Mails nach zu schliessen ("get rid of C._"), sei sogar von einem (mittelbaren) Beherrschungsverhältnis zwischen der BY._ Group a.s. und der C._ a.s. auszugehen, in welchem Fall Letztere und die Beschwerdegegnerin Schwestergesellschaften wären.
Die Behauptungen des Beschwerdeführers, mit denen er seinen Vorwurf der Befangenheit begründet, werden von der Beschwerdegegnerin bestritten.
3.2.2 Der Beschwerdeführer zeigt mit seinen Ausführungen keine Beziehung des Schiedsobmanns O._ zur Beschwerdegegnerin auf, die bei objektiver Betrachtung den Anschein der Befangenheit und die Gefahr der Voreingenommenheit begründen würde.
Abgesehen davon, dass aus den Ausführungen des Beschwerdeführers nicht hervorgeht, dass er den von ihm behaupteten Ablehnungsgrund dem Schiedsgericht sowie der Beschwerdegegnerin unverzüglich mitgeteilt hätte (vgl. <ref-law>), legt er insbesondere nicht substantiiert dar, inwiefern das Verhältnis der C._ a.s. mit der Beschwerdegegnerin bzw. Y._ derart sein soll, dass der Einsitz des Obmanns O._ im Verwaltungsrat der genannten Gesellschaft im vorliegenden Verfahren den Anschein der Befangenheit erwecken würde. Die vom Beschwerdeführer geschilderte Zusammenarbeit lässt nicht auf ein Verhältnis schliessen, das über gewöhnliche Geschäftsbeziehungen hinausgehen würde. Die Behauptung, die C._ a.s. werde von Y._ bzw. mit diesem verbundenen Personen beherrscht, ist spekulativ und wird vom Beschwerdeführer nicht hinreichend begründet. Entgegen seiner Ansicht lässt sich dem E-Mail der Anwaltskanzlei J._ vom 17. März 2006 kein Hinweis auf ein solches Beherrschungsverhältnis entnehmen. Die darin geäusserte Absicht der BY._ Group a.s., auf die Dienste der C._ a.s. aus Kostengründen zu verzichten und die erwähnte Forderung selbst geltend zu machen, weist nicht auf ein unmittelbares oder mittelbares Beherrschungsverhältnis hin.
Im Übrigen begründet weder der Umstand, dass sich die I._ a.s. in einem Schiedsverfahren von einer Anwaltskanzlei vertreten liess, die in Tschechien regelmässig auch die Interessen von Y._ und der mit ihm verbundenen Personen vertreten soll, noch die Tatsache, dass in besagtem Schiedsverfahren P._ als Obmann amtete, die Gefahr der Voreingenommenheit von O._ im vorliegenden Verfahren. Ebenso wenig gibt der blosse Umstand, dass O._ gemeinsam mit Personen im Verwaltungsrat einer Gesellschaft sass, die mit der B._ Limited eine Gesellschaft beherrschen sollen, die ihrerseits in einem Schiedsverfahren als Partei einer angeblich vom Beschwerdeführer errichteten Stiftung gegenüberstand, Anlass zu berechtigten Zweifeln an der Unabhängigkeit dieses Schiedsrichters im vorliegenden Verfahren.
Entgegen der in der Beschwerde geäusserten Ansicht kann nicht davon ausgegangen werden, dass aufgrund der geschilderten Verhältnisse eine gegenseitige Rücksichtnahme der beiden Schiedsrichter P._ und O._ sowie die "wohlwollende Berücksichtigung" der Interessen der Beschwerdegegnerin bzw. von Y._ "vorprogrammiert" seien. Die vom Beschwerdeführer vorgebrachten Behauptungen reichen nicht aus, um einen Anschein der Befangenheit (vgl. <ref-law>) zu erwecken.
4. Der Beschwerdeführer wirft der Vorinstanz eine Verletzung des Ordre public (<ref-law>) vor.
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). 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 Prinzipien 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. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff.; <ref-ruling> E. 6b S. 198; <ref-ruling> E. 6a S. 166 f.).
4.1 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). 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 Prinzipien 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. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 2.2 S. 392 ff.; <ref-ruling> E. 6b S. 198; <ref-ruling> E. 6a S. 166 f.).
4.2 4.2.1 Nicht einzugehen ist auf den unter dem Titel der Verletzung des Ordre public wiederum pauschal erhobenen Vorwurf der Befangenheit zweier Schiedsrichter. Auch mit dem Vorbringen, der dritte Schiedsrichter, Q._, habe den angefochtenen Schiedsentscheid nicht mitunterzeichnet, erhebt der Beschwerdeführer keine hinreichend begründete Rüge (Art. 77 Abs. 3 i.V.m. <ref-law>).
4.2.2 Der Grundsatz der Vertragstreue ist nur dann verletzt, wenn das Schiedsgericht zwar die Existenz eines Vertrags bejaht, die daraus sich ergebenden Konsequenzen jedoch missachtet, oder - umgekehrt - die Existenz eines Vertrags verneint, jedoch trotzdem eine vertragliche Verpflichtung bejaht (Urteile 4A_370/2007 vom 21. Februar 2008 E. 5.5; 4P.104/2004 vom 18. Oktober 2004 E. 6.3; vgl. auch BGE <ref-ruling> E. 6c/cc S. 171; <ref-ruling> E. 4b S. 638).
Der Beschwerdeführer legt nicht dar, inwiefern sich der angefochtene Schiedsspruch über diesen Grundsatz hinweggesetzt hätte. Er beanstandet vielmehr die rechtliche Beurteilung des Verhältnisses zwischen dem mit Y._ abgeschlossenen "Vertrag über Gemeinsames Vorgehen" und dem Kaufvertrag mit der Beschwerdegegnerin vom 9. November 2005 durch das Schiedsgericht. Er wirft der Vorinstanz dabei vor, sie habe ihrem Entscheid "eine von den tatsächlichen Vereinbarungen zwischen dem Beschwerdeführer, Y._ und der von diesem beherrschten Beschwerdegegnerin völlig abweichende Sichtweise zu Grunde gelegt" und zieht gestützt auf weitere, nach seiner Ansicht unhaltbare Feststellungen, vom angefochtenen Schiedsspruch abweichende Schlüsse. Der Beschwerdeführer setzt sich mit seinen Vorbringen, ohne eine zureichende Sachverhaltsrüge (vgl. vorn E. 2.4) zu erheben, über die für das Bundesgericht verbindlichen Sachverhaltsfeststellungen des Schiedsgerichts hinweg und verkennt gleichzeitig, dass eine falsche Vertragsauslegung für einen Verstoss gegen den Ordre public nicht ausreicht (BGE <ref-ruling> E. 4b S. 638; Urteile 4P.104/2004 vom 18. Oktober 2004 E. 6.3; 4P.62/1999 vom 26. Mai 1999 E. 1a/aa a.E.).
4.2.3 Das in der Beschwerdeergänzung behauptete widersprüchliche Verhalten vermag den Vorwurf des Rechtsmissbrauchs nicht zu begründen. Der Beschwerdeführer zeigt mit seinem Vorbringen, wonach sich die Beschwerdegegnerin - im Gegensatz zu Y._ in den beiden tschechischen Schiedsverfahren im Jahr 2007 - auf eine selbständige Erfüllbarkeit des Aktienkaufvertrags vom 9. November 2006 berufen habe, keine Unvereinbarkeit des angefochtenen Entscheids mit dem Ordre public (<ref-law>) auf.
Ebenso wenig zeigt der Beschwerdeführer eine Ordre public-Widrigkeit auf, wenn er vorbringt, seine Verpflichtung, der Beschwerdegegnerin seine 45 %-Beteiligung an der A._ Holding gegen einen Wechsel über CZK 1'182'500'000.-- zu überlassen, würde für ihn einen ökonomischen Unsinn bedeuten, dem er ohne die Gegenleistung von 50 % der Aktien der Beschwerdegegnerin nie zugestimmt hätte.
Eine Verletzung des Prinzips der Vertragstreue (pacta sunt servanda), des Rechtsmissbrauchsverbots bzw. des Grundsatzes von Treu und Glauben ist nicht dargetan.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Verfahrensausgang wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 75'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 85'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem ICC Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 11. Januar 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann