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. 