Sachverhalt:
A. A.a X._ AG (Klägerin) ist eine Aktiengesellschaft mit Sitz in Zug. Sie bezweckt hauptsächlich die Vermarktung von Werberechten im Bereich des Sports.
Federation Y._ mit Sitz in D._ (Beklagte) ist der nationale Fussballverband von E._. Sie organisiert unter anderem die Heimspiele der Nationalmannschaft von E._.
A.a Die Klägerin bzw. ihre Rechtsvorgängerin Z._ AG schloss am 6. November 2001 einen Vertrag mit der Beklagten ab, mit dem diese der Klägerin gewisse Übertragungs- und Werberechte an den Heimspielen der Nationalmannschaft von E._ für den Zeitraum vom 1. Januar 2002 bis 31. Dezember 2007 einräumte. Ziffer 11 dieses Vertrags sieht folgende Regelung zur Verlängerung der Geschäftsbeziehung zwischen den Parteien vor:
"11. Prolongation of the Contract
Federation Y._ shall present to Z._ AG on the basis of the Contract a proposal of the terms and conditions of a new contract ("Proposal") for the Matches of the National Team of E._ for the qualification of the World Cup 2010 (qualification period 01.01.2008 - 31.12.2009) and European Championship 2012 (qualification period 01.01.2010 - 31.12.2011), latest on 30 June 2007.
If Federation Y._ and Z._ AG can not agree on the terms and conditions of this new contract within two (2) months after Z._ AG has received the Proposal in writing, then Federation Y._ is free to enter into a new contract with any third party but only on the same or better terms and conditions as offered to Z._ AG in the Proposal, and only after giving Z._ AG the opportunity within seven (7) working days to accept such new terms.
If Federation Y._ fails to submit such a new Proposal for a Contract prior 30 June 2007 this Contract shall remain valid under the existing terms and conditions if Z._ AG confirms this by written notice by 31 August 2007, at the latest."
Der Vertrag vom 6. November 2001 enthält zudem folgende Schiedsklausel:
"... all disputes arising out of or in connection with the present Agreement shall be exclusively and finally settled under the Rules of Arbitration of the International Chamber of Commerce (Paris). Place of the arbitration shall be Zurich."
A.b Die Parteien führten ab Januar 2006 verschiedene Gespräche über eine mögliche Verlängerung ihrer Geschäftsbeziehung für den Zeitraum vom 1. Januar 2008 bis zum 31. Dezember 2011, der insbesondere die Qualifikationsspiele für die Weltmeisterschaft 2010 sowie die Europameisterschaft 2012 umfasst. Die Parteien erzielten jedoch keine Einigung.
Im Nachgang zu weiteren Gesprächen im Frühjahr 2007 legte die Klägerin der Beklagten am 13. Juni 2007 einen Entwurf für einen neuen Vertrag vor. Mit Schreiben vom 28. Juni 2007 stellte die Beklagte ihrerseits der Klägerin einen Vertragsentwurf zu, der auf einer Vertragsofferte der A._ AG, Wil/SG vom 26. Juni 2007 beruhte, einer anderen Sportrechtevermarkterin. Diese Vertragsofferte enthielt das Angebot der A._ AG, ein Freundschaftsspiel zwischen den Nationalmannschaften von E._ und F._ zu organisieren.
Die Klägerin informierte die Beklagte mit Schreiben vom 10. Juli 2007, dass sie an weiteren Verhandlungen über die Vertragsbedingungen interessiert sei. Da sich die Klägerin in jenem Zeitpunkt nicht darüber im Klaren war, ob die Offerte der Beklagten nach Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 lediglich die zweimonatige Verhandlungsfrist oder bereits die siebentägige Frist zur Annahme der Drittofferte auslöste und sich die Beklagte dazu nicht äusserte, erklärte die Klägerin zudem eventualiter die Annahme des Angebots der Beklagten vom 28. Juni 2007, allerdings ohne die Verpflichtung, ein Freundschaftsspiel gegen F._ zu organisieren.
Am 28./29. August 2007 fand ein Treffen zwischen den Parteien in D._ statt, anlässlich dessen auch Gespräche über die Bedingungen eines neuen Vertrags geführt wurden. Der Vertreter der Klägerin verliess das Treffen mit dem Eindruck, die Parteien hätten sich über den Abschluss eines neuen Vertrags auf Grundlage des Angebots der A._ AG vom 26. Juni 2007 geeinigt. Entsprechend bestätigte die Klägerin die Einigung mit Schreiben vom 30. August 2007 und kündigte an, der Beklagten sobald als möglich, einen schriftlichen Vertragsentwurf zuzustellen.
Wenige Stunden später informierte die Beklagte die Klägerin per Telefax über ihre Absicht, mit der A._ AG auf der Grundlage einer angepassten Vertragsofferte dieser Gesellschaft vom 30. August 2007 einen Vertrag abzuschliessen. Gemäss dieser neuen Offerte der A._ AG sollte das Freundschaftsspiel gegen F._ im Jahr 2008 in D._ stattfinden. Die Beklagte informierte die Klägerin im Weiteren über die Möglichkeit, gestützt auf Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 die Offerte der A._ AG vom 30. August 2007 innert sieben Tagen anzunehmen. Die genannte Vertragsofferte sah Zürich als Gerichtsstand vor.
Mit Schreiben vom 4. September 2007 stellte sich die Klägerin erneut auf den Standpunkt, die Parteien hätten bereits am 29. August 2007 einen neuen Vertrag geschlossen und fügte hinzu, dass sie der guten Ordnung halber die zweite Offerte der A._ AG gemäss Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 annehmen würde.
Mit Schreiben vom 5. September 2007 bestritt die Beklagte sowohl einen Vertragsabschluss in D._ am 29. August 2007 als auch die Gültigkeit der Annahme der neuen Offerte durch die Klägerin, da sie insbesondere deren Fähigkeit anzweifelte, das Freundschaftsspiel gegen F._ im Jahr 2008 in D._ zu organisieren. Die Beklagte erachtete daher die Annahme durch die Klägerin als ungültig.
Am 14. September 2007 schloss die Beklagte mit der A._ AG einen Vertrag auf Grundlage des Angebots vom 30. August 2007.
B. B.a Am 19. Oktober 2007 leitete die Klägerin das Schiedsverfahren gegen die Beklagte ein. Sie stellten dabei unter anderem die folgenden Rechtsbegehren:
"1. declare that the Contract between Respondent and Claimant (and originally signed by its predecessor Z._ AG) dated 6 November 2001 regarding the broadcasting, advertising and other rights in the home matches (qualification home games including play-offs and friendly matches) of Respondent's National Teams (Senior A-, U-21, Olympic- and Women-team) has been prolonged between Respondent and Claimant for the period of 1 January 2008 until 31 December 2011; and
declare in particular, that Claimant has validly acquired from Respondent
a) exclusive worldwide television and related media rights in any language and for all forms of audiovisual exhibition; and
b) advertising rights for all home games within the stadium for minimum uninterrupted 220 meters at the track side of the playing ground (110m touchline, 55m each goal line)
for all home matches (qualification home games including play-offs and friendly matches) of the national teams of E._ (Senior A-, U-21, Olympic- and Women-team) for the period of 1 January 2008 until 31 December 2011 and for the territory of the world (except the territory of E._ with regard to live rights); and
2. order Respondent to refrain from any actions which could jeopardize Claimant's rights under the Contract, in particular the rights described in plea for relief no. 1, and, in particular, from any actions which would directly or indirectly help making available such rights to a third party or which would assist such third party in marketing such rights; [...]."
Im Weiteren klagte sie auf Zahlung von Schadenersatz, wobei sie den Schadenersatzanspruch im Laufe des Verfahrens auf mindestens USD 3'447'557.-- bezifferte. Die Beklagte erhob ihrerseits Widerklage über USD 500'000.-- plus Zins.
B.b Das Schiedsgericht wies mit Schiedsspruch vom 12. Januar 2009 das Feststellungsbegehren der Klägerin bezüglich der behaupteten Verlängerung des Vertrags vom 6. November 2001 gemäss Rechtsbegehren Ziffer 1 Abs. 1 ab (Dispositiv-Ziffer 1). Weiter entschied es, dass es für die Beurteilung der Rechtsbegehren Ziffer 1 Abs. 2(a) und (b) sowie Ziffer 2 nicht zuständig sei (Dispositiv-Ziffern 2 und 3). Die Schadenersatzklage der Klägerin hiess das Schiedsgericht teilweise gut (Dispositiv-Ziffer 4), während es die Widerklage der Beklagten infolge Verrechnung mit der Schadenersatzforderung der Klägerin abwies (Dispositiv-Ziffer 5). Schliesslich entschied es über die Kosten und Entschädigungen des Schiedsverfahrens (Dispositiv-Ziffern 5 - 8) und wies sämtliche weiteren Klagen oder Verfahrensanträge der Parteien ab (Dispositiv-Ziffer 9).
Das Schiedsgericht erwog, dass zwischen den Parteien mit Annahmeerklärung der Klägerin vom 4. September 2007 ein neuer Vertrag zustande gekommen sei. Die Annahmeerklärung habe also nicht etwa zu einer Verlängerung des bestehenden Vertrags vom 6. November 2001 geführt; vielmehr sei dieser am 31. Dezember 2007 ausgelaufen. Der neue Vertrag vom 4. September 2007 enthalte keine Schiedsklausel, sondern eine Gerichtsstandsklausel. Da sich die Rechtsbegehren Ziffer 1 Abs. 2(a) und (b) sowie Ziffer 2 auf den neuen Vertrag vom 4. September 2007 stützten, sei für deren Beurteilung nicht das angerufene Schiedsgericht, sondern die ordentlichen Gerichte in Zürich zuständig.
Hinsichtlich des Schadenersatzbegehrens der Klägerin bejahte das Schiedsgericht seine Zuständigkeit und es erwog, dass die Beklag- te der Klägerin - vorbehältlich der Widerklage sowie der Verrechnungseinrede - den Betrag von USD 2'089'311.-- schulde. Im Weiteren erachtete es die Widerklageforderung der Beklagten über USD 500'000.-- plus Verzugszins von 5 % seit dem 19. Dezember 2007 (ausmachend USD 20'486.--) für grundsätzlich berechtigt, jedoch infolge Verrechnung per 16. Oktober 2008 untergegangen, weshalb es der Klägerin USD 1'568'825.-- zusprach und die Widerklage abwies.
C. Gegen den Schiedsspruch vom 12. Januar 2009 haben beide Parteien Beschwerde in Zivilsachen erhoben. Die Klägerin beantragt dem Bundesgericht, Dispositiv-Ziffern 2 und 3 des Schiedsspruchs seien aufzuheben und die Sache sei dem Einzelschiedsrichter zu neuer Beurteilung zurückzuweisen (4A_94/2009). Die Beklagte beantragt ihrerseits die Aufhebung des Schiedsspruchs vom 12. Januar 2009 (4A_96/2009). Beide Parteien schliessen in ihren Antworten je auf Abweisung der gegnerischen Beschwerde. Das Schiedsgericht hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Wenn - wie hier - an den Verfahren dieselben Parteien beteiligt sind und den Beschwerden der gleiche Sachverhalt zugrunde liegt, behandelt das Bundesgericht die verschiedenen Eingaben in der Regel in einem einzigen Urteil. Es rechtfertigt sich daher unter den gegebenen Umständen, die beiden Beschwerdeverfahren 4A_94/2009 und 4A_96/2009 zu vereinigen.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich in Zürich. Wenigstens eine Partei, vorliegend die Beklagte, hatte beim Abschluss der Schiedsvereinbarung ihren Sitz nicht in 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 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5; <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 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3b S. 382).
2.3 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. 105 Abs. 2 sowie Art. 97 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).
2.4 Die Parteien haben sich im Rahmen des Schiedsverfahrens geeinigt, dass die Streitsache nach Schweizer Recht entschieden werden soll (vgl. <ref-law>).
Beschwerde der Klägerin (4A_94/2009)
3. Die Klägerin macht unter Berufung auf <ref-law> geltend, die Vorinstanz hätte ihre Zuständigkeit mit Bezug auf die Rechtsbegehren Ziffer 1 Abs. 2 sowie Ziffer 2 zu Unrecht verneint.
3.1 Sie wirft der Vorinstanz eine unzutreffende Auslegung von Ziffer 11 des Vertrags vom 6. November 2001 vor. Durch Ausübung des in Abs. 2 dieser Bestimmung enthaltenen Eintrittsrechts werde nicht etwa ein neuer Vertrag abgeschlossen, sondern vielmehr der bisherige Vertrag fortgeführt. Grundlage sei die Verpflichtung in Ziffer 11 des Vertrags, die von Anfang an eine Pflicht der Beklagten zur Fortfüh-rung vorsehe. Diese Fortführungspflicht sei lediglich insofern abgeschwächt, als sich die Klägerin bessere Bedingungen des Marktes entgegenhalten lassen müsse. Diese Anpassung an veränderte bzw. bessere Marktbedingungen solle entweder auf dem Verhandlungswege oder durch Vorlage einer Drittofferte ermittelt werden. Im letzteren Fall stehe der Klägerin das Gestaltungsrecht zu, den Vertrag zu diesen (für die Beklagte) besseren Bedingungen fortzuführen.
Im Weiteren sehe Ziffer 11 Abs. 1 des Vertrags vom 6. November 2001 vor, dass die erste Offerte auf der Grundlage des bestehenden Vertrags unterbreitet werden müsse. Auch Ziffer 11 Abs. 2 sehe vor, dass die letzte Offerte die gleichen oder bessere Bedingungen enthalten müsse als die erste Offerte. Damit gehe Ziffer 11 implizit davon aus, es seien lediglich die kommerziellen Bedingungen neu auszuhandeln, während das "Gerüst" des Vertrags, wozu auch die Schiedsklausel gehöre, bestehen bleibe.
Schliesslich gelte auch aus prozessualer Sicht, dass die einmal begründete Zuständigkeit des Schiedsgerichts durch Veränderung der Umstände nicht mehr dahinfalle. Im Zeitpunkt der Einreichung der Schiedsklage am 19. Oktober 2007 sei allein die im Vertrag vom 6. November 2001 enthaltene Schiedsklausel relevant gewesen, denn die neuen Bestimmungen auf der Grundlage der Offerte der A._ AG deckten erst die Periode nach dem 1. Januar 2008 ab. Die ursprüngliche Gerichtsklausel sei sehr breit formuliert und solle alle Streitigkeiten erfassen, die sich aus dem Vertrag sowie im Zusammenhang mit dem Vertrag ergeben. Dazu gehörten sämtliche Fragen um die Fortführung des Vertrags vom 6. November 2001. Eine Spaltung der Zuständigkeit je nach Fragestellung sei durch die Formulierung der Schiedsklausel ausgeschlossen worden.
3.2 Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt, in rechtlicher Hinsicht frei. Demgegenüber überprüft es die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, 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; <ref-ruling> E. 2a S. 54).
3.2.1 Soweit in der Beschwerde vorgebracht wird, die Beklagte habe nie die Absicht kundgetan, mit der Klägerin einen neuen Vertrag abzuschliessen, ist darauf nicht einzutreten. Mit dieser Tatsachenbehauptung weicht die Klägerin vom vorinstanzlich festgestellten Sachverhalt ab, ohne dass eine rechtsgenügend begründete Sachverhaltsrüge erhoben würde. So hielt das Schiedsgericht etwa fest, dass die Beklagte der Klägerin mit Schreiben vom 28. Juni 2007 einen Vorschlag zum Abschluss eines neuen Vertrags für den Zeitraum vom 1. Januar 2008 bis 31. Dezember 2011 unterbreitete.
Ebenfalls unberücksichtigt zu bleiben hat das Vorbringen, es habe nie eine übereinstimmende gegenseitige Willensäusserung vorgelegen. Gemäss dem angefochtenen Entscheid waren sich die Parteien bei Abschluss des Vertrags vom 6. November 2001 einig, dass der Klägerin in Ziffer 11 Abs. 2 ein "Matching right" in dem Sinne eingeräumt werde, dass sie befugt sein solle, durch Annahmeerklärung innert sieben Tagen einen Vertragsabschluss zwischen den Parteien zu bewirken. Zudem hielt die Vorinstanz fest, die Beklagte habe der Klägerin das Angebot der A._ AG vorgelegt und die Klägerin habe dieses Angebot angenommen. Die Behauptung, es habe nie eine übereinstimmende gegenseitige Willenserklärung vorgelegen, lässt sich nicht auf den verbindlich festgestellten Sachverhalt des angefochtenen Entscheids stützen.
3.2.2 Die Klägerin bezeichnet die vorinstanzliche Auslegung von Ziffer 11 des Vertrags vom 6. November 2001, wonach die Parteien nicht den bestehenden Vertrag fortgesetzt, sondern einen neuen Vertrag geschlossen hätten, als falsch, ficht jedoch weder Dispositiv-Ziffer 1 des angefochtenen Entscheids an, mit dem die Vorinstanz das Begehren um Feststellung der angeblichen Verlängerung des Vertrags vom 6. November 2001 abgewiesen hat, noch setzt sie sich mit der ausführlichen Begründung des angefochtenen Entscheids auseinander. Vielmehr unterbreitet sie dem Bundesgericht lediglich die nach ihrer eigenen Ansicht zutreffende Auslegung der Vertragsklausel.
Unabhängig davon, ob die Klägerin damit überhaupt die gesetzlichen Anforderungen an eine rechtsgenügend begründete Rüge erfüllt (Art. 77 Abs. 3 i.V. mit <ref-law>), kann ihr nicht gefolgt werden. Die Vorinstanz hat mit überzeugenden Überlegungen ausgeführt, dass auf Grundlage einer objektivierten Auslegung der Willenserklärungen der Parteien davon auszugehen sei, dass durch Annahmeerklärung der Klägerin vom 4. September 2007 nicht eine Verlängerung des bestehenden Vertrags zu neuen Bedingungen, sondern vielmehr eine neue Vereinbarung zustande kam. So sehe zunächst Ziffer 11 Abs. 1 vor, dass die Beklagte spätestens bis zum 30. Juni 2007 einen Vorschlag der Bedingungen eines neuen Vertrags ("new contract") für die nächsten vier Jahre zu unterbreiten habe. Nach Abs. 2 dieser Vertragsklausel hätten die Parteien zudem während zweier Monate über die Bedingungen dieses neuen Vertrags ("this new contract") zu verhandeln. Beide Bestimmungen gingen davon aus, dass die Parteien, falls die Verhandlungen erfolgreich verliefen, einen neuen Vertrag abschliessen und nicht den bestehenden Vertrag mit veränderten Bedingungen weiterführen würden. Dieselbe Formulierung sei massgebend für den Fall, dass eine Einigung durch Ausübung des Eintrittsrechts ("matching right") der Klägerin nach Ziffer 11 Abs. 2 a.E. zustande komme. Diese Ansicht werde im Weiteren durch einen Vergleich der Absätze 1 und 2 mit Absatz 3 von Ziffer 11 bestätigt: Letztere Bestimmung sehe vor, dass der bestehende Vertrag bei Ausbleiben eines Angebots verlängert ("prolonged") werde, während in den anderen Fällen (Abs. 1 und 2) ein neuer Vertrag abzuschliessen sei. Dieses Auslegungsergebnis entspreche schliesslich auch dem Zweck der erwähnten Vertragsklausel: Beim Angebot an die Klägerin handle es sich um einen vollständig ausformulierten Vertragsentwurf, zumal dieser nach Scheitern der Verhandlungen - wie im vorliegenden Fall erfolgt - in Form eines verbindlichen Angebots einer Drittpartei vorzulegen sei, den die Klägerin entweder annehmen oder ablehnen könne.
Vorliegend ist weder dargetan noch ersichtlich, inwiefern die Vorinstanz mit diesen Erwägungen die von der Rechtsprechung entwickelten Grundsätze einer objektivierten Auslegung von Willenserklärungen (vgl. <ref-ruling> E. 2.2.1 S. 67 mit Hinweisen) verletzt hätte. Entgegen der Ansicht der Klägerin beschränkt sich der für die Fortfüh-rung der Geschäftsbeziehung vereinbarte Mechanismus von Ziffer 11 Abs. 2 des Vertrag vom 6. November 2001 insbesondere nicht darauf, lediglich die kommerziellen Bedingungen neu auszuhandeln, während das "Gerüst" des Vertrags (inklusive Schiedsklausel) bestehen bliebe. Vielmehr setzt das Eintrittsrecht nach Scheitern der Verhandlungen gerade voraus, dass ein umfassendes Angebot eines Dritten zum Abschluss eines neuen Vertrags vorliegt, zu dem auch die Regelung der Streiterledigung gehört.
Darüber hinaus führte die Vorinstanz unter Hinweis auf die Einvernahme von Herrn Marte aus, auch der Vertreter der Klägerin sei davon ausgegangen, dass mit der Annahmeerklärung vom 4. September 2007 ein neuer Vertrag zustande kommen sollte. Damit läge bereits ein tatsächlicher Konsens über die Frage der Natur des Vertragsabschlusses zwischen den Parteien vor, weshalb unabhängig von der Auslegung nach dem Vertrauensprinzip bereits aus diesem Grund vom Abschluss eines neuen Vertrags auszugehen wäre (<ref-ruling> E. 3.1 S. 632; <ref-ruling> E. 1a S. 73). Diese subjektive Vertragsauslegung beruht im Übrigen auf Beweiswürdigung, die der bundesgerichtlichen Überprüfung grundsätzlich entzogen ist (vgl. <ref-ruling> E. 3.1 S. 632 mit Hinweisen). Dass im zu beurteilenden Fall eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz gerechtfertigt wäre, macht die Klägerin nicht geltend. Ihre Rüge stösst daher auch aus diesem Grund ins Leere.
3.2.3 Auch aus dem von der Klägerin dargelegte Eventualstandpunkt lässt sich nichts zu ihren Gunsten ableiten. Entgegen der in der Beschwerde geäusserten Ansicht ist die Vorinstanz nicht davon ausgegangen, dass die bestehende Schiedsklausel im Vertrag vom 6. November 2001 durch eine neue Gerichtsstandsklausel mit Rückwirkung ersetzt worden wäre. Vielmehr hat die Vorinstanz klargestellt, dass Streitigkeiten, die sich aus dem neuen Vertrag ergeben, nicht mehr von der Schiedsklausel erfasst werden, während für Ansprüche aus dem Vertrag vom 6. November 2001 die Schiedsklausel massgebend bleibt.
Entgegen der Auffassung der Klägerin lässt sich aus dem Vertrag vom 6. November 2001 jedoch keine Pflicht ableiten, den nach Mass- gabe von Ziffer 11 Abs. 2 abgeschlossenen neuen Vertrag vom 4. September 2007 "tatsächlich zu erfüllen" bzw. "keine Tätigkeiten vorzunehmen, welche die Erfüllung behindern könnten". Für die Verletzung von Pflichten aus dem neuen Vertrag ist vielmehr die vereinbarte Gerichtsstandsklausel massgebend. Soweit die Klägerin die Feststellung von Ansprüchen für den Zeitraum vom 1. Januar 2008 bis 31. Dezember 2011 beantragt, die sich gegebenenfalls auf den neuen Vertrag zwischen den Parteien stützen lassen (siehe Rechtsbegehren Ziffer 1 Abs. 2), hat die Vorinstanz ihre Zuständigkeit zu Recht verneint. Auch hinsichtlich des beantragten Verbots bestimmter Handlungen der Beklagten, die diese Ansprüche gefährden könnten (Rechtsbegehren Ziffer 2), ist das Schiedsgericht zutreffend von seiner Unzuständigkeit ausgegangen. Daran ändern auch die prozessualen Überlegungen der Klägerin nichts, zumal es im zu beurteilenden Fall überhaupt nicht um die Frage geht, ob eine einmal begründete Zuständigkeit durch Veränderung der Umstände dahinfallen kann, sondern um die Abgrenzung der Zuständigkeit zur Beurteilung von Ansprüchen, die sich auf verschiedene Verträge mit unterschiedlichen Schieds- bzw. Gerichtsstandsklauseln stützen.
Beschwerde der Beklagten (4A_96/2009)
4. Die Beklagte beantragt in allgemeiner Weise die Aufhebung des Schiedsspruchs vom 12. Januar 2009. Ihre Rügen beschränken sich jedoch auf den der Klägerin zugesprochenen Schadenersatzanspruch (Dispositiv-Ziffer 4). Auch in ihren Ausführungen zur Beschwerdelegitimation erwähnt die Beklagte lediglich ihre Verpflichtung aufgrund des Schiedsspruchs zur Zahlung von Schadenersatz im Betrag von USD 1'568'825.--. Da die Vorinstanz die Feststellungs- bzw. Unterlassungsbegehren (Rechtsbegehren Ziffern 1 und 2) der Klägerin entweder abgewiesen hat (Dispositiv-Ziffer 1) oder darauf mangels Zuständigkeit nicht eingetreten ist (Dispositiv-Ziffern 2 und 3) wäre diesbezüglich auch die Beschwerdelegitimation der Beklagten zu verneinen.
Das Schiedsgericht hat sich zudem für die Beurteilung der Widerklage der Beklagten, die mit dem Qualifikationsspiel vom 21. November 2007 für die Europameisterschaft 2008 in Zusammenhang steht und sich auf den Vertrag vom 6. November 2001 stützt, für zuständig erachtet und die Widerklage infolge Verrechnung abgewiesen (Dispositiv-Ziffer 5). Die Frage, ob ein Schiedsgericht zur Behandlung der Verrechnungseinrede befugt ist, wenn die Verrechnungsforderung von der Schiedsabrede nicht gedeckt ist, wird kontrovers diskutiert (dazu etwa Anton Heini, in: Zürcher Kommentar zum IPRG, 2. Aufl. 2004, N. 6b ff. zu <ref-law>; Frank Vischer und andere, Internationales Vertragsrecht, 2. Aufl. 2004, Rz. 1134 ff.; Werner Wenger/Markus Schott, in: Basler Kommentar zum IPRG, 2. Aufl. 2007, N. 41 ff. zu <ref-law>; Felix Dasser, in: Basler Kommentar zum IPRG, 2. Aufl. 2007, N. 19 ff. zu <ref-law>; Christoph Zimmerli, Die Verrechnung im Zivilprozess und in der Schiedsgerichtsbarkeit, 2003, S. 187 ff.). Die Beklagte äussert sich jedoch nicht zu dieser Frage. Soweit die Klägerin der Widerklageforderung ihre Schadenersatzforderung verrechnungsweise entgegenhält, erhebt die Beklagte somit keine hinreichende Zuständigkeitsrüge nach <ref-law> (Art. 77 Abs. 3 i.V.m. <ref-law>).
Im Folgenden wird daher davon ausgegangen, dass sich die Beschwerde auf die Anfechtung von Dispositiv-Ziffern 4 sowie 6 - 8 des Schiedsspruchs beschränkt.
5. Die Beklagte rügt unter Hinweis auf <ref-law>, die Vorinstanz habe sich für die Beurteilung der in der Folge zugesprochenen Schadenersatzforderung zu Unrecht für zuständig erklärt.
5.1 Die Vorinstanz erwog, dass sie zur Beurteilung des Schadenersatzbegehrens nur insoweit zuständig sei, als dessen Anspruchsgrundlage im Vertrag vom 6. November 2001 liege, der eine Schiedsklausel enthalte. Dies ergebe sich ohne Weiteres aus dem Umstand, dass die Annahmeerklärung der Klägerin vom 4. September 2007 keine Verlängerung des Vertrags vom 6. November 2001 bewirkte, sondern das Zustandekommen eines neuen Vertrags.
Die Vorinstanz stellte darauf ab, dass sich der Schadenersatzanspruch auf eine behauptete Verletzung von Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 durch die Beklagte stütze. Das Schiedsgericht erwog, dass die Klägerin mit Erklärung vom 4. September 2007 wirksam ihr Eintrittsrecht ("matching right") ausgeübt habe. Indem sich die Beklagte geweigert habe, die Wirksamkeit der Annahme der Klägerin zu anerkennen, habe sie das Ergebnis des Vertragsmechanismus von Ziffer 11 Abs. 2 missachtet. Damit habe sie eine vertragliche Bestimmung verletzt, nämlich die Bindung an das Drittangebot ("the duty of being bound by the third-party offer"), das die Beklagte der Klägerin am 30. August 2007 übermittelte und das von der Klägerin am 4. September 2007 bedingungslos angenommen wurde. Eine weitere Verletzung von Ziffer 11 sei darin zu erkennen, dass die Beklagte am 14. September 2007 eine Vereinbarung über denselben Gegenstand mit einer Drittpartei abgeschlossen habe, obwohl sie an die wirksam ausgeübte Annahmeerklärung der Klägerin gebunden gewesen sei.
Gestützt auf diese Überlegungen sprach die Vorinstanz der Klägerin Schadenersatz für entgangenen Gewinn im Zusammenhang mit dem Qualifikationsspiel für die Weltmeisterschaft 2010 zwischen E._ und G._ zu, das am 15. Oktober 2008 in D._ ausgetragen wurde.
5.2 Wie die Beklagte gegen diese Erwägungen zu Recht einwendet, stellt ihr beschriebenes Verhalten richtig besehen nicht eine Verletzung von Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 dar, sondern gegebenenfalls eine Verletzung des neuen Vertrags, der die Übertragungs- und Werberechte für den Zeitraum vom 1. Januar 2008 bis 31. Dezember 2011 zum Gegenstand hat. Soweit nach dem angefochtenen Entscheid durch die rechtswirksame Ausübung des Eintrittsrechts ("matching right"), also durch einseitige Willenserklärung der Klägerin, ein neuer Vertrag zwischen den Parteien zustande kam, war ein weiteres Zutun der Beklagten weder erforderlich noch vertraglich geschuldet. Gestützt auf das Gestaltungsrecht der Klägerin kam ein Vertragsabschluss vielmehr gerade unabhängig vom Einverständnis der Beklagten zustande. Diese war nach Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001 lediglich verpflichtet, der Klägerin eine Drittofferte vorzulegen, um ihr damit die Ausübung des Eintrittsrechts und somit den Vertragsabschluss innert sieben Tagen zu ermöglichen. Wie sich aus den tatsächlichen Feststellungen des angefochtenen Entscheids ergibt, ist die Beklagte dieser Verpflichtung nachgekommen, indem sie der Klägerin die Drittofferte der A._ AG unterbreitete.
Eine Verletzung des Vertragsmechanismus nach Ziffer 11 Abs. 2, die zu einer Schadenersatzpflicht führen würde, ist daher nicht ersichtlich. Indem die Beklagte die Wirksamkeit der Annahmeerklärung durch die Klägerin und damit das Zustandekommen des neuen Vertrags verneinte, verletzte sie entgegen der Annahme der Vorinstanz sowie der Klägerin keine in Ziffer 11 Abs. 2 begründete Verpflichtung zur Bindung an die Drittofferte. Vielmehr wäre durch Ausübung des Eintrittsrechts ("matching right") infolge Annahmeerklärung vom 4. September 2007 unbesehen der Rechtsauffassung der Beklagten ein neuer Vertrag zustande gekommen, aus dem sich wiederum neue Verpflichtungen hinsichtlich der Übertragungs- und Werberechte für den Zeitraum vom 1. Januar 2008 bis 31. Dezember 2011 ergeben. Soweit sich die Beklagte nicht an die in der Drittofferte enthaltenen Verpflichtungen gebunden fühlte und diesen nicht nachgekommen sein sollte, verletzte sie womöglich den neuen Vertrag mit der Klägerin vom 4. September 2007, nicht aber die Bestimmung von Ziffer 11 Abs. 2 des Vertrags vom 6. November 2001, die lediglich einen formellen Mechanismus zur allfälligen Fortführung der Geschäftsbeziehung vorsieht, sich jedoch über den genauen Inhalt sowie die Bedingungen der zukünfti gen Beziehung ausschweigt. Ebenso wenig verletzte die Beklagte Ziffer 11, wenn sie am 14. September 2007 mit einer Drittpartei einen Vertrag für den Zeitraum nach dem 31. Dezember 2007 abschloss, zumal der Klägerin die Drittofferte vertragsgemäss bereits am 30. August 2007 unterbreitet und von dieser am 4. September 2007 angenommen wurde. Auch in diesem Zusammenhang verletzte die Beklagte gegebenenfalls den Vertrag vom 4. September 2007.
5.3 Der von der Vorinstanz zugesprochene Schadenersatz für entgangenen Gewinn aus dem Qualifikationsspiel für die Weltmeisterschaft 2010 zwischen E._ und G._ vom 15. Oktober 2008 lässt sich nach dem Gesagten allenfalls auf den Vertrag zwischen den Parteien vom 4. September 2007 stützen, der die Übertragungs- und Werberechte an den Heimspielen der Nationalmannschaft von E._ für den Zeitraum vom 1. Januar 2008 bis 31. Dezember 2011 umfasst, nicht jedoch auf den Vertrag vom 6. November 2001, der der Klägerin die Rechte für den Zeitraum vom 1. Januar 2002 bis zum 31. Dezember 2007 einräumte und per 31. Dezember 2007 auslief. Der angefochtene Schiedsspruch erweist sich insoweit auch als widersprüchlich, indem er aufgrund der Gerichtsstandsklausel zugunsten der Zürcher Gerichte einerseits die Zuständigkeit für die Feststellung von Ansprüchen bezüglich der Heimspiele für den Zeitraum nach dem 1. Januar 2008 - durchaus zutreffend (dazu vorn E. 3) - verneinte, sich jedoch andererseits für die Beurteilung von Schadenersatzansprüchen aus dem Heimspiel vom 15. Oktober 2008 für zuständig erachtete.
Die Vorinstanz hat sich daher für die Beurteilung der Schadenersatzklage zu Unrecht für zuständig erklärt. Daran vermag auch der Einwand der Klägerin nichts zu ändern, die Beklagte habe im ganzen vorinstanzlichen Verfahren nie geltend gemacht, der Einzelschiedsrichter sei zur Beurteilung des Schadenersatzbegehrens nicht zuständig, soweit dieses auf dem Vertrag vom 6. November 2001 beruhe, womit sie sich auf das Verfahren eingelassen habe. Gemäss dem angefochtenen Entscheid hat sich die Beklagte bereits im vorinstanzlichen Verfahren auf die Unzuständigkeit der Vorinstanz berufen, soweit sich das Schadenersatzbegehren auf den neuen Vertrag stütze. Entgegen der Ansicht der Klägerin ist die Frage, ob sich der Schadenersatzanspruch auf den Vertrag vom 6. November 2001 stützen lässt, der im Gegensatz zum neuen Vertrag vom 4. September 2007 eine Schiedsklausel enthält, als materielle Vorfrage der Zuständigkeitsrüge (<ref-law>) einer Überprüfung durch das Bundesgericht zugänglich (siehe vorn E. 3.2).
5.4 Bei diesem Ergebnis erübrigt es sich, auf die weiteren Rügen der Beklagten einzugehen, dem Einzelschiedsrichter habe die Zuständigkeit zur Beurteilung der Schadenersatzklage auch wegen der Überschreitung der Klagesumme von USD 1 Mio. gemäss der vereinbarten Schiedsklausel (Ziffer 13.8 des Vertrags vom 6. November 2001) gefehlt bzw. die Vorinstanz habe ihren Gehörsanspruch verletzt.
6. Die Beschwerde der Klägerin erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Demgegenüber ist die Beschwerde der Beklagten gutzuheissen, Dispositiv-Ziffern 4 sowie 6 - 8 des angefochtenen Entscheids sind aufzuheben und die Sache ist zu neuer Entscheidung über die Kosten und Entschädigungen an die Vorinstanz zurückzuweisen.
Dem Ausgang des Verfahrens entsprechend wird die Klägerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Das Bundesgericht erkennt:
1. Die Verfahren 4A_94/2009 und 4A_96/2009 werden vereinigt.
2. Die Beschwerde der Klägerin (4A_94/2009) wird abgewiesen, soweit darauf einzutreten ist.
3. Die Beschwerde der Beklagten (4A_96/2009) wird gutgeheissen, Dispositiv-Ziffern 4 sowie 6 - 8 des Schiedsspruchs vom 12. Januar 2009 werden aufgehoben und die Sache wird zu neuer Entscheidung über die Kosten und Entschädigungen an die Vorinstanz zurückgewiesen.
4. Die Gerichtskosten von Fr. 26'000.-- werden der Klägerin auferlegt.
5. Die Klägerin hat die Beklagte für das bundesgerichtliche Verfahren mit Fr. 30'000.-- zu entschädigen.
6. Dieses Urteil wird den Parteien und dem ICC Schiedsgericht mit Sitz in Zürich schriftlich mitgeteilt.
Lausanne, 9. Juni 2009
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann