Sachverhalt:
A. Am 3. Mai 1999 schloss die Y._ AG (Beschwerdegegnerin) mit A._ einen, mit B._ drei und mit X._ (Beschwerdeführer) vier schriftliche Vermögensverwaltungsverträge ab. Im Jahr 2002 traten auf den verwalteten Vermögen erhebliche Verluste ein.
B. Am 31. Oktober 2005 klagte der Beschwerdeführer beim Handelsgericht des Kantons Zürich gegen die Beschwerdegegnerin auf Zahlung von Schadenersatz im Umfang von Fr. 2'955'884.-- nebst Zins zu 5 % seit dem 30. Dezember 2002 sowie von vorprozessualen Anwaltskosten im Umfang von Fr. 60'000.-- nebst Zins zu 5 % seit dem 28. Oktober 2005. Das Handelsgericht wies die Klage mit Urteil vom 5. Februar 2008 ab.
Die dagegen eingelegte Nichtigkeitsbeschwerde wies das Kassationsgericht des Kantons Zürich mit Zirkulationsbeschluss vom 17. März 2009 ebenfalls ab, soweit es darauf eintrat.
C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei das Urteil des Handelsgerichts des Kantons Zürich vom 5. Februar 2008 aufzuheben und die Beschwerdegegnerin zur Zahlung von Fr. 2'955'884.-- nebst Zins zu 5 % seit dem 30. Dezember 2002 zu verurteilen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde, nachdem das Bundesgericht ihr Gesuch um Sicherstellung einer allfälligen Parteientschädigung mit Verfügung vom 20. Juli 2009 gutgeheissen hat. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1.1).
1.1 Gegenstand des Verfahrens bildet eine Zivilsache (<ref-law>). Die Rechtsbegehren des Beschwerdeführers sind im kantonalen Verfahren nicht geschützt worden (<ref-law>), der massgebende Streitwert beträgt mehr als Fr. 30'000.-- (Art. 51 i.V.m. <ref-law>) und die Beschwerdefrist ist eingehalten (<ref-law>).
1.2 Die Beschwerde in Zivilsachen ist nur gegen Entscheide letzter kantonaler Instanzen zulässig (<ref-law>). Gegen das angefochtene Urteil des Obergerichts ist die kantonale Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich nach <ref-law>/ZH zulässig. Der angefochtene Entscheid ist deshalb insoweit nicht kantonal letztinstanzlich, als er vom Kassationsgericht überprüft werden kann. Nach <ref-law>/ZH kann mit Nichtigkeitsbeschwerde geltend gemacht werden, der angefochtene Entscheid beruhe zum Nachteil des Nichtigkeitsklägers auf einer Verletzung eines wesentlichen Verfahrensgrundsatzes (Ziff. 1), auf einer aktenwidrigen oder willkürlichen tatsächlichen Annahme (Ziff. 2) oder auf einer Verletzung klaren materiellen Rechts (Ziff. 3). Ausgeschlossen ist die Nichtigkeitsbeschwerde, wenn das Bundesgericht einen Mangel frei überprüfen kann, wobei sie gemäss <ref-law>/ZH stets zulässig ist, wenn eine Verletzung von Art. 8, 9, 29 oder 30 BV oder von Art. 6 EMRK geltend gemacht wird.
Das angefochtene Urteil des Handelsgerichts stellt daher insoweit keinen kantonal letztinstanzlichen Entscheid dar, als geltend gemacht wird, das Handelsgericht habe offensichtlich unrichtige Sachverhaltsfeststellungen getroffen oder den Verfahrensgrundsatz von Treu und Glauben verletzt (<ref-law>/ZH; FRANK/STRÄULI/MESSMER, Kommentar zur zürcherischen Zivilprozessordnung, 3. Aufl. 1997, N. 16 zu § 281). Entsprechende Rügen hätte der Beschwerdeführer gegen den - vorliegend nicht angefochtenen - Entscheid des Kassationsgerichts vorbringen müssen. Im Rahmen der Beschwerde gegen das Urteil des Handelsgerichts kann auf sie nicht eingetreten werden.
1.3 Nach <ref-law> ist in der Beschwerdeschrift in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Soweit das Bundesgericht das Recht von Amtes wegen anwendet (<ref-law>), ist zwar eine ausdrückliche Nennung bestimmter Gesetzesartikel nicht erforderlich, falls aus den Vorbringen hervorgeht, gegen welche Regeln des Bundesrechts die Vorinstanz verstossen haben soll. Unerlässlich ist aber, dass auf die Begründung des angefochtenen Urteils eingegangen und im Einzelnen dargetan wird, worin eine Verletzung von Bundesrecht liegen soll (<ref-ruling> E. 3.3 S. 60; <ref-ruling> E. 1.4; vgl. <ref-ruling> E. 2a S. 400).
Diesen Anforderungen genügt die Beschwerdeschrift nur teilweise: Auf einen rechtstheoretischen Vorspann, in dem der Beschwerdeführer dem Bundesgericht die Grundlagen der Rechtsanwendungslehre präsentiert, folgen über weite Strecken rein appellatorische Ausführungen, indem einfach pauschal "Rechtsanwendungsfehler", oder eine "übermächtige Einseitigkeit der Urteilsfindung" gerügt und der Vorinstanz allgemein ein "Falsch-Verstehen zentraler Sachbehauptungen", ein "fehlgeleitetes Sachverhaltsverständnis", eine "unrichtige Optik" bzw. die Einnahme einer "falschen Perspektive"vorgeworfen werden. Auf solche Rügen kann nicht eingetreten werden.
2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören nicht nur die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, sondern auch jene über den Ablauf der vorinstanzlichen Verfahren, also die Feststellungen über den Prozesssachverhalt (faits de la procédure; fatti procedurali; teilweise auch als "Prozessstoff" oder "Prozesstatbestand" bezeichnet; vgl. zum Ganzen BERNARD CORBOZ, in: Commentaire de la LTF, 2009, N. 31 zu <ref-law>; YVES DONZALLAZ, Loi sur le Tribunal fédéral, Commentaire, Bern 2008, N. 3672 zu <ref-law>; JEAN-FRANÇOIS POUDRET, Commentaire de la loi fédérale d'organisation judiciaire, Bd. 2, 1990, N. 4.2 zu Art. 63 aOG; BIRCHMEIER, Handbuch des Bundesgesetzes über die Organisation der Bundesrechtspflege, S. 89; HENRI DESCHENAUX, La distinction du fait et du droit dans les procédures de recours au Tribunal fédéral, Diss. Fribourg 1948, S. 19). Zum Prozesssachverhalt gehören namentlich die Anträge der Parteien, ihre Tatsachenbehauptungen, rechtlichen Erörterungen (BIRCHMEIER, a.a.O.; CORBOZ, a.a.O.), Prozesserklärungen und Beweisvorbringen (DONZALLAZ, a.a.O.), der Inhalt einer Zeugenaussage, einer Expertise oder die Feststellungen anlässlich eines Augenscheins (CORBOZ, a.a.O.).
Die Feststellung des Sachverhalts kann 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>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2). Da willkürliche Sachverhaltsfeststellungen vorliegend nur gegen den Entscheid des Kassationsgerichts gerügt werden könnten, sind die tatsächlichen Feststellungen des Handelsgerichts für das Bundesgericht verbindlich.
Diese Grundsätze verkennt der Beschwerdeführer, soweit er sich in seiner Beschwerde auf von ihm angeblich vor Handelsgericht vorgetragene Tatsachenbehauptungen stützt, die gemäss dem vorinstanzlich festgestellten Prozesssachverhalt entweder gar nicht oder nicht mit dem vom Beschwerdeführer behaupteten Inhalt vorgebracht wurden. Auf die entsprechenden Rügen ist nicht einzutreten.
3. Das Handelsgericht ist im Wesentlichen zum Schluss gelangt, dass der klägerische Tatsachenvortrag in sich widersprüchlich bzw. fragmentarisch sei. Der Beschwerdeführer komme teilweise nicht einmal seiner abstrakten Behauptungslast, geschweige denn der Substanziierungslast nach, weshalb er nach der Zürcher Praxis gar nicht erst zum Beweis zuzulassen und die Klage abzuweisen sei. Der Beschwerdeführer rügt, die Vorinstanz habe damit die bundesrechtlichen Grundsätze zur Behauptungs- und Substanziierungslast verletzt. Zudem habe sie die Behauptungslast falsch verteilt.
3.1 Das Handelsgericht stellte folgenden Prozesssachverhalt fest: Während der Beschwerdeführer in seiner Klageschrift noch vorgebracht habe, es sei ein einziger Vermögensverwaltungsvertrag - nämlich zwischen ihm und der Beschwerdegegnerin - zustande gekommen, habe er in der Replik behauptet, es lägen acht verschiedene Vermögensverwaltungsverträge vor, jeweils ergänzt durch von ihm erteilte Weisungen und Auflagen. Letztere seien im Zeitraum zwischen dem 30. Juni bis 27. Dezember 2002 verletzt worden, was zum eingeklagten Schaden geführt habe.
Gemäss dem Handelsgericht ergibt sich aus diesen Behauptungen kein schlüssiger Tatsachenvortrag. Zwar leite der Beschwerdeführer in der Replik seine Schadenersatzansprüche und die entsprechenden Haftungsvoraussetzungen aus jeweils einem der acht Vermögensverwaltungsverträge her, beziehe sich in seinen Ausführungen aber zugleich auf ein angeblich bestehendes "integrales" bzw. ein "zwischen den vier Parteien vereinbartes Vermögensverwaltungsverhältnis" und behaupte, die angeblichen missachteten Weisungen und Auflagen seien in das "integrale Vermögensverwaltungsverhältnis" eingegangen, ohne dass er einen Bezug zu einem konkreten Vertragsverhältnis (insb. einem der acht schriftlichen Verträge) dartue. Der Beschwerdeführer habe nicht behauptet, wer wann wem welche Weisung betreffend welches Vertragsverhältnis erteilt habe.
3.2 In Verfahren, die vom Verhandlungsgrundsatz beherrscht sind, tragen die Parteien die Verantwortung für die Beschaffung des Tatsachenstoffes. Sie haben dem Gericht die Tatsachen, auf die sie ihre Begehren stützen, darzulegen und die Beweismittel anzugeben (vgl. nun Art. 55 Abs. 1 der auf Anfang 2011 in Kraft tretenden Schweizerischen Zivilprozessordnung vom 19. Dezember 2008 [BBl 2009 S. 21]). Die Parteien trifft die sog. Behauptungslast (fardeau de l'allégation; onere dell'allegazione). Welche Tatsachen zu behaupten sind, hängt vom Tatbestand der Norm ab, auf welche der geltend gemachte Anspruch abgestützt wird. Die Parteien haben alle Tatbestandselemente der materiellrechtlichen Normen zu behaupten, die den von ihnen anbegehrten Anspruch begründen (vgl. Fabienne Hohl, Procédure civile, Bd. I, 2001, N. 796; Jürgen Brönnimann, Die Behauptungslast, in: Leuenberger [Hrsg.], Der Beweis im Zivilprozess, 2000, S. 57).
Der Behauptungslast ist Genüge getan, wenn die Parteien in ihrem Tatsachenvortrag in allgemeiner Weise sämtliche Tatsachen benennen, welche unter die ihr Begehren stützenden Normen zu subsumieren sind. Ein solchermassen vollständiger Tatsachenvortrag wird als schlüssig bezeichnet, da er bei Unterstellung, er sei wahr, den Schluss auf die anbegehrte Rechtsfolge zulässt (vgl. Brönnimann, a.a.O., S. 57). Bestreitet der Prozessgegner den schlüssigen Tatsachenvortrag der behauptungsbelasteten Partei, greift eine über die Behauptungslast hinausgehende Substanziierungslast. Die Vorbringen sind diesfalls nicht nur in den Grundzügen, sondern in Einzeltatsachen zergliedert so umfassend und klar darzulegen, dass darüber Beweis abgenommen oder dagegen der Gegenbeweis angetreten werden kann (<ref-ruling> E. 2b S. 368).
3.3 Da sich der Gegenstand der Behauptungs- und Substanziierungslast nach der materiellrechtlichen Anspruchsgrundlage richtet, bestimmen für Rechtsverhältnisse des Bundesprivatrechts die anwendbaren Normen des Bundesrechts, welche Tatsachen zu behaupten und zu substanziieren sind (vgl. <ref-ruling> E. 2b S. 368; <ref-ruling> E. 3e S. 188; <ref-ruling> E. 2b S. 339; Hohl, a.a.O., N. 796; Brönnimann, a.a.O., S. 56). Dagegen bleibt es dem kantonalen Prozessrecht überlassen, ob es eine Ergänzung der Substanziierung im Beweisverfahren zulassen oder diese bereits im Behauptungsstadium in einer Weise verlangen will, welche die Überprüfung der Sachvorbringen im Beweisverfahren erlaubt (BGE <ref-ruling> E. 3 S. 341 f.).
3.4 Der Beschwerdeführer hat das Zustandekommen eines (wie auch immer gearteten) Vermögensverwaltungsverhältnisses behauptet. Nach der bundesgerichtlichen Rechtsprechung untersteht die Vermögensverwaltung den auftragsrechtlichen Regeln (<ref-ruling> E. 2b; <ref-ruling> E. 1). Durch die Annahme eines Auftrages verpflichtet sich der Beauftragte, die ihm übertragenen Geschäfte oder Dienste vertragsgemäss zu besorgen (<ref-law>). Hat der Auftraggeber für die Besorgung des übertragenen Geschäftes eine Weisung gegeben, so darf der Beauftragte nur insofern davon abweichen, als nach den Umständen die Einholung einer Erlaubnis nicht tunlich und überdies anzunehmen ist, der Auftraggeber würde sie bei Kenntnis der Sachlage erteilt haben (<ref-law>). Der Beauftragte haftet dem Auftraggeber für getreue und sorgfältige Ausführung des ihm übertragenen Geschäfts (<ref-law>). Er hat grundsätzlich nicht für den Erfolg seiner Tätigkeit einzustehen. Haftungsbegründend ist vielmehr eine unsorgfältige oder treuwidrige und den Auftraggeber schädigende Ausführung des Auftrages.
Aus den massgebenden bundesrechtlichen Normen ergibt sich daher im vorliegenden Fall, dass der Beschwerdeführer, der von der Beschwerdegegnerin Ersatz für erlittenen Schaden verlangen will, den Bestand des Vermögensverwaltungsvertrages, dessen sorgfalts- bzw. weisungswidrige Ausführung, den Umfang des Schadens sowie den Kausalzusammenhang zwischen der Sorgfaltswidrigkeit und dem Schadenseintritt zu behaupten hat.
3.5 Wie bereits vor der Vorinstanz stellt der Beschwerdeführer auch vor Bundesgericht widersprüchliche Tatsachenbehauptungen auf. Zum einen macht er geltend, es habe "materiell ein einziges Vermögensverwaltungsverhältnis" bestanden, das "auf die drei Parteien A._, B._ und X._ ausstrahlte". Zum anderen spricht er vom Bestand von "formell drei Vermögensverwaltungsverhältnissen", um dann wiederum die Unterzeichnung von acht Verträgen zu behaupten. Dabei zeigt der Beschwerdeführer nicht auf, in welchem Zusammenhang diese Vertragsverhältnisse untereinander stehen. Es bleibt jedenfalls unklar, was der Beschwerdeführer unter einem "integralen Ansatz" bzw. einer "panoptischen Sichtweise" verstehen und welche Konsequenzen er daraus ableiten will. Er legt nicht dar, bezogen auf welchen Vertrag er welche schadenersatzauslösende Vertragsverletzung geltend machen will, bzw. auf welchen Vertrag sich die angeblich missachteten Weisungen bezogen haben sollen. Obwohl er dafür entgegen der in seiner Beschwerde teilweise vertretenen Auffassung die Behauptungslast trägt, benennt der Beschwerdeführer mithin nicht einmal widerspruchsfrei den Bestand eines konkreten Vertrages, aus dessen Verletzung er Ansprüche ableiten will. Damit lässt sich sein Tatsachenvortrag auch unter keine vertragliche Anspruchsgrundlage subsumieren. Das Handelsgericht hat folglich kein Bundesrecht verletzt, wenn es die Klage mangels Schlüssigkeit des Tatsachenvortrags abgewiesen hat.
3.6 Nichts zu seinen Gunsten ableiten kann der Beschwerdeführer namentlich auch aus dem Schreiben vom 29. April 1999, welches seiner Ansicht nach Weisungen enthalten habe, die von der Beschwerdegegnerin angeblich missachtet worden seien. Nach den verbindlichen Sachverhaltsfeststellungen des Handelsgerichts steht einzig fest, dass zwischen der Beschwerdegegnerin einerseits und dem Beschwerdeführer bzw. A._ und B._ andererseits insgesamt acht schriftliche Vermögensverwaltungsverträge abgeschlossen wurden. Das Schreiben vom 29. April 1999 ist gemäss der Vorinstanz jedoch nicht zum Vertragsinhalt geworden. Zudem leitet der Beschwerdeführer keinen konkret bezifferten Schaden aus dem Schreiben ab, weshalb gemäss der zutreffenden Ansicht der Vorinstanz offen bleiben kann, ob sich das Schreiben allenfalls auf einen anderen, wie auch immer gearteten Vertrag bezieht. Nichts ableiten kann der Beschwerdeführer schliesslich auch aus den Schreiben, mit denen er sog. Stopp-Loss-Marken festgesetzt habe. Gemäss den Feststellungen der Vorinstanz haben diese Schreiben jedenfalls keine verbindlichen Weisungen enthalten, die dort erwähnten Vermögenstitel bei einem Verlust von 5 % zwingend zu verkaufen. Das Handelsgericht hat deshalb zu Recht ausgeführt, dass aus der Verletzung von Regeln, die gar nicht Vertragsinhalt wurden, keine Ansprüche abgeleitet werden können.
4. Der Beschwerdeführer rügt weiter eine Verletzung seines Rechts auf Beweis sowie der Beweislastregeln gemäss <ref-law>.
4.1 Das aus <ref-law> abgeleitete Recht auf Beweis erstreckt sich nur auf rechtserhebliche Tatsachen, d.h. auf Sachumstände, von deren Verwirklichung es abhängt, ob so oder anders zu entscheiden ist (<ref-ruling> E. 2.6 S. 24; <ref-ruling> E. 4a S. 317; <ref-ruling> E. 2b S. 40; je mit Hinweisen). Ergibt die vom Gericht vorzunehmende Prüfung des Tatsachenvortrags, dass es den Parteivorbringen insgesamt an Schlüssigkeit gebricht, dann sind auch die vorhandenen Tatsachenbehauptungen nicht erheblich, womit die Beweisabnahme unterbleiben kann (Jürgen Brönnimann, Die Behauptungs- und Substanzierungslast im schweizerischen Zivilprozessrecht, 1989, S. 198).
4.2 Die Tatsachenbehauptungen des Beschwerdeführers lassen sich unter keine bundesrechtliche, insbesondere vertragsrechtliche Anspruchsgrundlage subsumieren. Da der Tatsachenvortrag somit den Schluss auf die anbegehrte Rechtsfolge nicht zulässt, ist unerheblich, ob sich die behaupteten Tatsachen ereignet haben. Die Beweisabnahme darüber erübrigt sich. Sowohl die Regeln über die Beweislastverteilung als auch der Beweisanspruch nach <ref-law> werden gegenstandslos.
5. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Damit erübrigt sich die Prüfung der Rügen, die der Beschwerdeführer gegen die (nicht entscheidtragende) Alternativbegründung der Vorinstanz vorgebracht hat.
Dem Verfahrensausgang entsprechend wird der Beschwerdeführer für das bundesgerichtliche Verfahren kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG). Die Parteientschädigung ist aus der vom Beschwerdeführer an die Gerichtskasse bezahlten Sicherheitsleistung auszurichten.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 20'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 22'000.-- zu entschädigen. Diese Entschädigung wird aus der an die Gerichtskasse bezahlten Sicherheitsleistung ausgerichtet.
4. Dieses Urteil wird den Parteien und dem Handelsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 7. April 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Hurni