Sachverhalt:
A. X._ (mit Wohnsitz im Kanton Graubünden) als Kreditnehmer und die Y._ Ltd., Britische Jungferninseln, als Kreditgeberin haben am 7. September 2003 einen Darlehensvertrag (Facility Agreement) über rund fünf Millionen US-Dollar abgeschlossen. Partei dieses Vertrages ist auch die AX._ Ltd., Jersey, welche Eignerin eines gleichnamigen, in Jersey registrierten Segelschiffs vom Typ eines zweimastigen Schoners ist. Das gesamte Gesellschaftskapital der AX._ Ltd. ist in zwei Aktien zum Nominalwert von je einem britischen Pfund verbrieft, welche von den zwei Gesellschaften BX._ Ltd. und CX._ Ltd., Jersey, treuhänderisch für X._ gehalten werden.
Am 31. Dezember 2004 sind X._ und die Y._ Ltd. eine mit dem Darlehensvertrag zusammenhängende Vereinbarung (Equitable Charge) eingegangen, deren Zweck darin besteht, die Verpflichtungen von X._ aus dem Darlehensvertrag zu Gunsten der Kreditgeberin abzusichern. Als Sicherheit dienen die beiden vorgenannten Aktien der AX._ Ltd.
Der Darlehensvertrag wurde in der Folge mehrmals angepasst und erneuert, zuletzt am 27. Dezember 2006 durch das "Amended and Restated Facility Agreement". Auf den gleichen Zeitpunkt wurde die Sicherungsvereinbarung erneuert (Amended and Restated Equitable Charge).
Sowohl für den Darlehens- wie für den Sicherungsvertrag haben die Parteien eine Rechtswahl zugunsten des englischen Rechts getroffen.
B. Im Januar 2010 beschloss die Y._ Ltd., von X._ die Rückzahlung des Darlehens auf dem Rechtsweg einzufordern. Nachdem das Kantonsgericht Graubünden einen ersten Zahlungsbefehl für nichtig erklärt und einen zweiten als mangelhaft aufgehoben hatte, stellte das Betreibungsamt B._ (mittlerweile Betreibungsamt Z._) am 15. Juli 2010 in der ordentlichen Betreibung auf Pfändung Nr. _ über eine Forderung von insgesamt Fr. 6'110'861.-- zuzüglich Zins erneut einen Zahlungsbefehl aus. Dieser wurde am 10. August 2010 zugestellt, worauf X._ am 19. August 2010 Rechtsvorschlag erhob.
C. Am gleichen Tag erhob X._ gegen die Aus- und Zustellung des Zahlungsbefehls Beschwerde an das Kantonsgericht von Graubünden als Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen. Er beantragte, die Betreibung auf dem Weg der Pfandverwertung fortzusetzen. Das Kantonsgericht wies die Beschwerde mit Entscheid vom 4. Februar 2011 ab.
D. X._ (Beschwerdeführer) hat am 3. März 2011 Beschwerde an das Bundesgericht erhoben. Er beantragt die Aufhebung des angefochtenen Entscheides. Zudem sei gerichtlich anzuordnen, dass die in Frage stehende Betreibung der Y._ Ltd. (Beschwerdegegnerin) auf dem Wege der Pfandverwertung fortzusetzen sei. Eventuell sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Am 8. März 2011 hat der Beschwerdeführer zudem um aufschiebende Wirkung ersucht.
Nachdem das Kantonsgericht hinsichtlich der aufschiebenden Wirkung auf Stellungnahme verzichtet und die Beschwerdegegnerin sich ablehnend geäussert hat, ist der Beschwerde mit Präsidialverfügung vom 21. März 2011 aufschiebende Wirkung zuerkannt worden.
In der Sache hat das Betreibungsamt Z._ auf Vernehmlassung verzichtet; die Beschwerdegegnerin und das Kantonsgericht beantragen Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. Die Beschwerde in Zivilsachen ist gegen den Entscheid der kantonal letztinstanzlichen Aufsichtsbehörde in Schuldbetreibungs- und Konkurssachen (<ref-law>) unabhängig vom Streitwert zulässig (Art. 72 Abs. 2 lit. a und Art. 74 Abs. 2 lit. c BGG). Sie ist binnen Frist erfolgt (<ref-law>). Die vorliegende Eingabe ist demnach als Beschwerde in Zivilsachen entgegenzunehmen.
Mit der Beschwerde können Rechtsverletzungen gemäss Art. 95 f. BGG gerügt werden. Die falsche Anwendung des massgebenden ausländischen Rechts kann allerdings in vermögensrechtlichen Angelegenheiten nicht vorgebracht werden (<ref-law> e contrario), sondern es kann einzig dessen willkürliche Anwendung (<ref-law>) geltend gemacht werden (allgemein <ref-ruling> E. 3.1 S. 447 f.; zum Aufsichtsverfahren Urteil 5A_205/2009 vom 6. August 2009 E. 5.1). Die Feststellung des Sachverhalts kann schliesslich nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Dabei bedeutet "offensichtlich unrichtig" willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis).
Die Beschwerde ist zu begründen (<ref-law>). Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Ansonsten kann auf die Beschwerde nicht eingetreten werden (<ref-ruling> E. 2.1 S. 245 f.). Strengere Anforderungen gelten bei Verfassungsrügen, welche in der Beschwerde präzise vorgebracht und begründet werden müssen (<ref-law>; <ref-ruling> E. 1.4 S. 400 f.; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen). Wird eine Verletzung des Willkürverbots - einschliesslich der Willkür bei der Sachverhaltsfeststellung (BGE <ref-ruling> E. 1.4.3 S. 255) - geltend gemacht, muss der Beschwerdeführer klar und detailliert anhand der Erwägungen des angefochtenen Urteils aufzeigen, in welcher Hinsicht der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 2.2 S. 246 mit Hinweis; vgl. <ref-ruling> E. 4.3 S. 522).
2. Nicht mehr Gegenstand des bundesgerichtlichen Verfahrens bilden der Zeitpunkt der Ausstellung des Zahlungsbefehls während der Betreibungsferien sowie die internationale Zuständigkeit des Betreibungsamts Z._ zur Durchführung des Betreibungsverfahrens. Einzig zur Diskussion steht noch, ob sich der Beschwerdeführer zu Recht auf die Einrede der Vorausvollstreckung in die Pfandsicherheit (beneficium excussionis realis; <ref-law>) beruft.
2.1 Die Vorinstanz hat diese Einrede aus mehreren Gründen verworfen. In der Hauptbegründung hat sie ausgeführt, der Beschwerdegegnerin stehe kein Pfandrecht im Sinne von Art. 37 und 41 SchKG sowie <ref-law> zu bzw. kein dingliches Sicherungsmittel, welches einem Pfandrecht schweizerischen Verständnisses weitgehend entspreche. Gegenstand der Sicherheit seien vorliegend Aktien; in Frage komme also nur ein Fahrnispfandrecht, dessen Begründung Besitzübertragung verlange. Das dem schweizerischen Faustpfandrecht entsprechende dingliche Sicherungsmittel des Common Law sei die pledge (auch pawn genannt). Vorliegend sei im Vertrag jedoch durchwegs von "equitable charge", "securities" und "charged property" die Rede und es sei nicht ohne weiteres anzunehmen, dass die englische Rechtsberatungsfirma, welche die Verträge erstellt habe, unpräzise Begriffe gewählt habe. Eine equitable charge sei nun jedoch eine Sicherungsbestellung ohne Sicherungsübereignung und ohne Einräumung des Besitzes. Aus den Akten gehe denn auch nicht hervor, dass sich die beiden zur Sicherung verwendeten Aktien bei der Y._ Ltd., an ihrer Adresse in A._ auf der Isle of Man, befinden würden. Vielmehr ist die Vorinstanz davon ausgegangen, die Aktien befänden sich nach wie vor auf den Kanalinseln.
In einer ersten Eventualerwägung hat das Kantonsgericht erwogen, eine Berufung auf das beneficium excussionis realis sei nur möglich, wenn das Pfand in der Schweiz oder in einem Staat liege, der dieses Institut ebenfalls kenne. Die Sicherheit sei im Vereinigten Königreich, genauer auf den Kanalinseln gelegen und die Parteien hätten sowohl im Darlehens- wie im Sicherungsvertrag eine Rechtswahl zugunsten des englischen Rechts getroffen. Wenn entgegen dem bisher Ausgeführten angenommen würde, dass die equitable charge einem schweizerischen Faustpfand gleichgestellt sei und die equitable charge es dem Sicherungsnehmer erlaube, einen gerichtlichen Befehl oder eine Vollstreckungsmassnahme zu erwirken, die darin gipfle, dass das Pfand versilbert und der Gläubiger daraus befriedigt werde, so müsste der Beschwerdeführer darlegen, dass das englische Recht ein dem beneficium excussionis realis vergleichbares Rechtsinstitut kenne. Das auf die Sicherheit anwendbare Sachstatut bestimme, ob dem Schuldner die entsprechende Einwendung zustehe. Der Beschwerdeführer habe dies aber nicht darzulegen versucht und die Existenz einer solchen Einrede im englischen Recht ergebe sich auch nicht aus den Akten.
In einer weiteren Eventualerwägung hat die Vorinstanz schliesslich ausgeführt, selbst wenn die equitable charge ein Pfandrecht nach schweizerischem Rechtsverständnis wäre und das englische Recht eine dem beneficium excussionis realis entsprechende Rechtsfigur kennen würde, könnte sich der Beschwerdeführer nicht auf diese Einrede berufen, wenn die beiden Aktien bloss als subsidiäre Sicherheit bestellt worden wären, der Schuldner auf die Einrede vertraglich verzichtet hätte oder dem Gläubiger die freie Wahl hinsichtlich des Vollstreckungsweges zustünde. Ob die Sicherheit subsidiärer Natur sei, hat das Kantonsgericht in der Folge offen gelassen. Hingegen würden Einwendungsverzicht des Schuldners und freies Wahlrecht der Gläubigerin leicht erkennbar aus Abschnitt 8 des Facility Agreements hervorgehen. Zudem hätten die Parteien im Sicherungsvertrag der Gläubigerin das Recht eingeräumt, die als Sicherheit dienenden Aktien selber zu verkaufen, was die Einwendung des beneficium excussionis realis ebenfalls ausschliesse.
2.2 Der Beschwerdeführer rügt zunächst, die Vorinstanz habe offensichtlich unrichtig festgestellt, die Beschwerdegegnerin sei nicht im Besitz der fraglichen Aktien. Die Beschwerdegegnerin habe in ihrer Beschwerdeantwort an das Kantonsgericht zugegeben, dass sich die Aktien an ihrer Adresse auf der Isle of Man befinden würden. Des Weiteren lasse die Sicherungshinterlegung ein Pfandrecht entstehen. Die Beschwerdegegnerin könne umfassend über die verpfändeten Wertpapiere verfügen, während er (der Beschwerdeführer) keine Verfügungsgewalt mehr darüber habe. Aus Ziff. 7.1 des Sicherungsvertrages ergebe sich, dass das Pfand nicht nur subsidiär hafte. Schliesslich habe es die Vorinstanz unterlassen zu prüfen, ob eine verbotene Verfallsabrede nach <ref-law> vorliege. Die vorliegend im Sicherungsvertrag getroffene Regelung komme einer Verfallsabrede gleich, da die Beschwerdegegnerin die Aktien auch auf sich selbst übertragen könne und keine Pflicht zur Abrechnung ersichtlich sei. Eine Verfallsabrede widerspreche dem Ordre public. Es sei deshalb angezeigt, eine Pfandverwertung anzuordnen.
3. Die Beschwerde genügt den Begründungsanforderungen nicht. Was zunächst die Hauptbegründung der Vorinstanz betrifft, hat die Beschwerdegegnerin zwar tatsächlich in ihrer Beschwerdeantwort vor Kantonsgericht anerkannt und vor Bundesgericht bestätigt, dass die als Sicherheit dienenden Aktien an ihrer Adresse auf der Isle of Man verwahrt werden. Eine formelle Berichtigung der vorinstanzlichen Sachverhaltsfeststellung erübrigt sich jedoch, da es nicht entscheidend darauf ankommt (<ref-law>), ob sich die Aktien nach wie vor auf den Kanalinseln befinden, wie die Vorinstanz angenommen hat, oder auf die Isle of Man in den Machtbereich der Beschwerdegegnerin verbracht wurden, wie die Parteien insoweit übereinstimmend vorbringen. Der Beschwerdeführer legt nämlich einerseits nicht dar, wieso der Besitzübergang etwas an der von der Vorinstanz erläuterten Rechtsnatur der equitable charge ändern sollte, zumal das Kantonsgericht festgehalten hat, dass die Aktien nach dem Vertrag nicht ursprünglich, d.h. als Wirksamkeitsvoraussetzung der Sicherheitsbestellung, in den Besitz der Beschwerdegegnerin überzugehen hatten. Andererseits beruht das angefochtene Urteil auf mehreren (Eventual-)begründungen, die je für sich den Rechtsstreit vor der Vorinstanz hätten beenden können. In einem solchen Fall muss in der Beschwerde dargelegt werden, dass jede von ihnen Recht verletzt; andernfalls kann auf die Beschwerde nicht eingetreten werden (<ref-ruling> E. 6.3 S. 120 f.). Zur ersten Eventualbegründung äussert sich der Beschwerdeführer nicht. Die Vorinstanz ist darin von der konstanten bundesgerichtlichen Rechtsprechung zu im Ausland gelegenen bzw. vom ausländischen Recht beherrschten Pfandobjekten ausgegangen. Danach setzt eine erfolgreiche Berufung auf das beneficium excussionis realis voraus, dass die betreffende Rechtsordnung eine <ref-law> entsprechende Einrede ebenfalls vorsieht (BGE 36 I 337 E. 1 und 2 S. 339 f.; 65 III 92 E. 2 S. 94; 68 III 131 S. 134). Der Beschwerdeführer wendet sich mit keinem Wort gegen die diesbezüglichen vorinstanzlichen Erwägungen. Gemäss Kantonsgericht hätte er den Nachweis eines entsprechenden Instituts im englischen Recht erbringen müssen, was er nicht einmal versucht habe, und auch aus den Akten lasse sich das Bestehen einer entsprechenden Einrede im englischen Recht nicht ableiten. Ficht der Beschwerdeführer diese Überlegungen nicht an, erübrigt es sich, auf die weiteren Ausführungen des Beschwerdeführers zur angeblichen Verfallsabrede einzugehen. Seine Darlegungen hiezu beziehen sich nicht auf die Frage der Existenz einer <ref-law> entsprechenden Einrede im englischen Recht, sondern auf die letzte Eventualerwägung der Vorinstanz, worin das Kantonsgericht festgehalten hat, der Beschwerdeführer habe ohnehin vertraglich auf ein allfälliges beneficium excussionis realis verzichtet bzw. die Parteien hätten weitgehende Freiheit der Beschwerdegegnerin in der Wahl des Vollstreckungswegs vereinbart.
4. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten. Eine Ausscheidung der Kosten des Verfahrens zur Gewährung aufschiebender Wirkung rechtfertigt sich nicht (<ref-law>). Zudem hat der Beschwerdeführer die Beschwerdegegnerin angemessen zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 10'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin mit Fr. 20'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Betreibungsamt Z._ und dem Kantonsgericht von Graubünden, Schuldbetreibungs- und Konkurskammer als Aufsichtsbehörde über Schuldbetreibung und Konkurs, schriftlich mitgeteilt.
Lausanne, 3. Mai 2011
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Hohl Zingg