Sachverhalt:
A. Die X._ AG (im Folgenden: X._ AG bzw. Beschwerdeführerin) arbeitete seit den späten 1990er-Jahren unter dem Titel "a._" an einem Projekt für den Bau eines Parkhauses unter der ...strasse in Basel. Mit diesem Projekt gelangte sie an das damalige Baudepartement des Kantons Basel-Stadt (BD; heute Bau- und Verkehrsdepartement, BVD). In der Folge traten auch andere Projektträger mit Projekten für unterirdische Parkinganlagen an die Behörden heran (Projekte "b._" und "c._"). Der Regierungsrat des Kantons Basel-Stadt erklärte in Beantwortung einer parlamentarischen Anfrage am 1. November 2006, er unterstütze die Realisierung eines der von privater Seite lancierten Parking-Projekte; er werde sie dem Grossen Rat nach dem von ihm zu treffenden Variantenentscheid vorlegen. Am 16. Februar 2007 informierte das BD die Projektträger, dass eine neutrale Bewertungsstudie der verschiedenen Projekte erarbeitet werden sollte. Diese Beurteilung erfolgte zu Beginn des Jahres 2008. In der Folge traf das BD weitere Abklärungen. Am 23. Dezember 2008 informierte der Regierungsrat, dass er als Ergebnis einer umfassenden Evaluationsstudie das Projekt "d._" dem Projekt "c._" vorziehe; das Projekt "b._" war zuvor zurückgezogen worden.
Später kam der Regierungsrat auf seinen Entscheid zurück und bestätigte am 13. Mai 2009 gegenüber der X._ AG, dass der Variantenentscheid wieder offen sei. Am 11. Juni 2010 informierte der Kantonsbaumeister die X._ AG über den am 18. Mai 2010 erfolgten Beschluss des Regierungsrates, das Projekt "c._" weiterverfolgen zu wollen. Auf Ersuchen der X._ AG hin teilte der Departementsvorsteher dieser am 17. August 2010 den Beschluss des Regierungsrates vom 18. Mai 2010 mit, stellte aber klar, dass der Regierungsrat damit lediglich die von privater Seite vorgelegten Projektideen beurteilt und daraus Schlussfolgerungen für die eigene weitere Planung gezogen habe. Auf Anfrage hin teilte das BVD der X._ AG mit, beim Entscheid des Regierungsrates vom 18. Mai 2010 handle es sich nicht um eine anfechtbare Verfügung, sondern nur um eine Ermächtigung an das BVD, die erforderlichen Entscheidgrundlagen für den Grossen Rat auszuarbeiten; der Abschluss von Verträgen mit einer Trägerschaft sei erst nach einer Beschlussfassung des Grossen Rates möglich.
B. Am 24. September 2010 erhob die X._ AG Rekurs beim Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und beantragte, das BVD sei anzuweisen, seinen Vergabeentscheid gegenüber der Rekurrentin ordnungsgemäss zu eröffnen. Eventuell sei ein allfällig bereits ergangener Vergabeentscheid aufzuheben und die Sache zur Neubeurteilung an das BVD zurückzuweisen; subeventualiter sei die Rechtswidrigkeit des Vergabeentscheids festzustellen. Das Verwaltungsgericht lud die Y._ AG zum Verfahren bei. Am 16. November 2010 verbot es dem Kanton vorläufig, Nutzungsrechte an der Allmend für die Errichtung oder den Betrieb eines unterirdischen Parkings im Planungsperimeter des Projekts "e._" zu verleihen. Mit Urteil vom 25. November 2011 wies das Verwaltungsgericht den Rekurs ab.
C. Die X._ AG erhebt am 24. Februar 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten sowie subsidiäre Verfassungsbeschwerde an das Bundesgericht. Sie beantragt, das Urteil des Verwaltungsgerichts vom 25. November 2011 sei aufzuheben und der Beschwerdegegner sei anzuweisen, seinen Vergabeentscheid gegenüber der Beschwerdeführerin ordnungsgemäss zu eröffnen. Eventualiter sei der Beschwerdegegner anzuweisen, einen allfällig ergangenen Vergabeentscheid aufzuheben und die Sache neu zu beurteilen. Zudem beantragt sie aufschiebende Wirkung und vorsorgliche Massnahmen.
D. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. Das BVD beantragt, auf die Beschwerde nicht einzutreten, eventuell sie abzuweisen. Die Y._ AG verzichtet auf Vernehmlassung.
Mit Verfügung vom 12. April 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch um aufschiebende Wirkung bzw. vorsorgliche Massnahmen abgewiesen.
Mit weiteren Eingaben vom 12. Juli und 26. Juli 2012 halten die Parteien an ihren Anträgen fest.
Erwägungen:
1. 1.1 Mit dem angefochtenen Entscheid stellt die Vorinstanz fest, das BVD habe mit seiner Weigerung, im heutigen Zeitpunkt die Konzessionsvergabe in Form einer anfechtbaren Verfügung zu erlassen, keine Rechtsverweigerung begangen. Das ist ein kantonal letztinstanzlicher Endentscheid, gegen den grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Art. 90 BGG). Auch soweit es um die Anwendbarkeit des öffentlichen Beschaffungsrechts geht, ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, da der geschätzte Wert des Projekts den Schwellenwert gemäss Art. 83 lit. f Ziff. 1 BGG übersteigt und mit der Frage, wie weit das öffentliche Beschaffungsrecht auf Vorhaben der vorliegenden Art anwendbar ist, eine Rechtsfrage von grundsätzlicher Bedeutung aufgeworfen wird (Art. 83 lit. f Ziff. 2 BGG; vgl. Urteil 2C_484/2008 vom 9. Januar 2009 E. 1.3.2, nicht publ. in: BGE 135 II 49; Urteil 2C_116/2007 vom 10. Oktober 2007 E. 4).
1.2 Die Beschwerde setzt ein aktuelles und praktisches Rechtsschutzinteresse voraus (Art. 89 Abs. 1 lit. c BGG). Der Beschwerdegegner bestreitet ein solches Interesse der Beschwerdeführerin, weil der allenfalls bestehende Anspruch auf Erlass einer anfechtbaren Verfügung bzw. auf Durchführung eines Vergabeverfahrens jedenfalls verfrüht geltend gemacht werde und die Beschwerdeführerin ihre Rechte in einem späteren Verfahrensschritt geltend machen könne. Indessen ist hier die Frage, in welcher Verfahrensphase die behaupteten Ansprüche bestehen, gerade die Streitfrage, welche von der Beschwerdeführerin aufgeworfen wird. Sie ist bei Beschwerden, mit denen eine Rechtsverweigerung gerügt wird, nicht im Rahmen des Eintretens, sondern der materiellen Beurteilung zu entscheiden. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher einzutreten.
1.3 Die Verfassungsbeschwerde ist im Verhältnis zur Beschwerde in öffentlich-rechtlichen Angelegenheiten subsidiär (Art. 113 BGG). Da hier die Letztere zur Verfügung steht, ist die vom Beschwerdeführer gleichzeitig erhobene Verfassungsbeschwerde nicht zulässig, weshalb darauf nicht eingetreten werden kann.
2. Das Bundesgericht prüft frei und von Amtes wegen die richtige Anwendung von Bundes- und Völkerrecht (Art. 95 lit. a und b bzw. Art. 106 Abs. 1 BGG). Die Verletzung von Grundrechten sowie von kantonalem und interkantonalem Recht überprüft es nur auf Rüge hin (Art. 106 Abs. 2 BGG). Es legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat; die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 BGG).
3. 3.1 Streitgegenstand bildet die Frage, ob hier ein (anfechtbarer) Vergabeentscheid vorliegt oder ein solcher hätte getroffen werden müssen. Es ist unbestritten, dass für die Realisierung des fraglichen Parkings eine Konzession für die Benützung öffentlichen Bodens erforderlich ist. Die Beschwerdeführerin ist der Auffassung, die Erteilung dieser Konzession unterstehe dem öffentlichen Vergaberecht und der Ausschreibungspflicht gemäss Art. 2 Abs. 7 des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt (Binnenmarktgesetz, BGBM; SR 943.02).
3.2 Das Verwaltungsgericht hat erwogen, es stelle sich die Frage, ob für die Erteilung einer solchen Konzession direkt die Verfahrensregeln des Beschaffungsrechts oder Art. 2 Abs. 7 BGBM zur Anwendung gelangten (vgl. angefochtener Entscheid E. 2.1). Ersteres sei zu verneinen (vgl. E. 2.3) und Letzteres könne offen bleiben (vgl. E. 3.2). Der Bau der streitigen Anlage setze verschiedene rechtliche Entscheide voraus, für welche das BVD nicht zuständig sei. So sei für eine Konzession für die Benützung des öffentlichen Bodens der Grosse Rat zuständig. Davon könne nur abgesehen werden, wenn in einem gesetzmässig aufgestellten Bebauungsplan die Inanspruchnahme der Allmend vorgesehen sei; zum Erlass eines entsprechenden Bebauungsplans sei der Grosse Rat unter Vorbehalt des Referendums zuständig. Sodann setze das Projekt eine Änderung des kantonalen Gesetzes gegen den Bau von öffentlichen Autoparkgaragen in der Innenstadt voraus, wozu wiederum der Grosse Rat unter Vorbehalt des Referendums zuständig sei (vgl. E. 3.3.2). Diese Zuständigkeit des Grossen Rates schliesse zwar die vorgängige Durchführung eines Vergabeverfahrens nicht zwingend aus, doch könnte ein Zuschlag nur unter Vorbehalt der genannten Beschlüsse durch den Grossen Rat bzw. das Volk erfolgen. Müsste ein Zuschlag unter einem solchen Vorbehalt erfolgen, so könne in dessen Aufschub bis zu den entsprechenden Beschlüssen der zuständigen Staatsorgane keine Rechtsverzögerung oder Rechtsverweigerung erblickt werden (vgl. E. 3.3.3). Zudem seien die verschiedenen Projekte zwar im Raum "e._" angesiedelt, aber an verschiedenen Standorten; sie hätten auch in verschiedener Hinsicht unterschiedliche Auswirkungen (vgl. E. 3.4.1-3.4.3). Dieser Standortentscheid sei nicht im Vergabeverfahren zu entscheiden, sondern im Rahmen eines raumplanungsrechtlichen Planungsentscheides, der in der Kompetenz des Grossen Rates liege; der Regierungsrat sei nur zur Vorbereitung dieses Entscheids zuständig, doch könne sein Variantenentscheid den Grossen Rat und das Volk nicht binden und habe daher nicht den Charakter einer Verfügung (vgl. E. 3.4.4). Beim raumplanerischen Standortentscheid komme den zuständigen Planungsorganen ein erhebliches Planungsermessen zu. Dieses Planungsermessen könne zum vornherein nicht durch einen Vergabeentscheid eingeschränkt werden. Eine Ausschreibung und ein Zuschlagsentscheid vor dem Standortentscheid seien daher letztlich sinn- und zwecklos (vgl. E. 3.4.5). Sodann erscheine das Verfahren zur Vorbereitung des Standortentscheids insgesamt als transparent und diskriminierungsfrei, so dass die am Verfahren beteiligte Rekurrentin gar keinen praktischen Nutzen an einer Ausschreibung substantiieren könne (vgl. E. 3.5). Schliesslich habe das BVD auch nicht gegen die raumplanungsrechtliche Koordinationspflicht verstossen, zumal es die Projektträgerschaften in das Planungsverfahren einbezogen habe (vgl. E. 3.6). Zusammenfassend habe das BVD mit der Weigerung, zum aktuellen Zeitpunkt die Konzessionsvergabe in Form einer anfechtbaren Verfügung zu erlassen, keine Rechtsverweigerung begangen. Ob nach erfolgtem Standortentscheid des Grossen Rates oder des Volkes gestützt auf Art. 2 Abs. 7 BGBM eine Ausschreibung der Vergabe des öffentlichen Grundes durchgeführt werden müsse, könne offen bleiben (vgl. E. 3.7).
3.3 Im Folgenden zu prüfen ist somit - abgesehen von der Feststellung des Sachverhalts (vgl. E. 4 hiernach) - in einem ersten Schritt die Frage, ob auf den vorliegenden Sachverhalt das öffentliche Beschaffungsrecht anwendbar ist (vgl. E. 5 hiernach). Diese Grundsatzfrage ist vorab zu klären, da sie die Vorinstanz verneint hat und die Beschwerdeführerin diesen Schluss rügt. Die Anwendung des Vergaberechts würde das bisherige Vorgehen des Kantons denn auch ganz grundsätzlich in Frage stellen. In einem zweiten Schritt ist sodann zu untersuchen, ob im vorliegenden Fall die Ausschreibungspflicht des Art. 2 Abs. 7 BGBM zur Anwendung kommt (vgl. E. 6 hiernach). Diese zweite Frage ist dabei unabhängig von der ersten Frage der Anwendbarkeit des Vergaberechts zu prüfen.
4. Die Beschwerdeführerin rügt eine offensichtlich unrichtige Sachverhaltsfeststellung.
4.1 Sie macht geltend, die Vorinstanz habe nicht auf die Schreiben der früheren Regierungsrätin Schneider vom 16. Februar 2007 und die Medienmitteilung vom 9. Mai 2008 Bezug genommen, woraus sich ergebe, dass der Beschwerdegegner eine Ausschreibung vorgenommen habe. Die Vorinstanz hat zwar im angefochtenen Entscheid unter dem Sachverhalt diese beiden Dokumente erwähnt. Ob jedoch aus diesen Dokumenten zu folgern ist, dass eine Ausschreibung vorgenommen werden müsste, ist nicht eine Frage der Sachverhaltsfeststellung, sondern der rechtlichen Würdigung (vgl. E. 6.2 hiernach).
4.2 Die Beschwerdeführerin bringt weiter vor, aus dem Protokoll des Hochbau- und Planungsamtes vom 8. Mai 2008 gehe hervor, dass der endgültige Vertrag zwischen Kanton und Investor abgeschlossen sein soll, wenn der Ratschlag an den Grossen Rat überwiesen werde; die Vorinstanz habe willkürlich ausgeführt, dieses Protokoll ändere nichts daran, dass ein raumplanerischer Entscheid vorliege. Auch hierbei handelt es sich in erster Linie um eine Frage der rechtlichen Qualifikation. Im Übrigen macht die Beschwerdeführerin nicht geltend, dass ein Vertrag, wie er im erwähnten Protokoll in Aussicht gestellt wurde, abgeschlossen worden wäre.
4.3 Die Beschwerdeführerin rügt, die Vorinstanz habe willkürlich festgestellt, es handle sich um einen raumplanerischen bzw. Standortentscheid; aus den Vorgaben vom 2. Juni 2008 für die zweite Bewerbungsrunde, der Zusammenstellung der Rahmenbedingungen vom 23. Dezember 2009 sowie dem Regierungsratsbeschluss vom 18. Mai 2010 und der Rekursantwort vom 15. Dezember 2010 gehe hervor, dass es um ein konkretes Projekt und um Vertragsverhandlungen mit dem Projektträger gehe. Die Vorinstanz hat ihre Beurteilung, es gehe hier um einen Standort- bzw. Planungsentscheid wie folgt begründet: Die Projekte hätten verschiedene Standorte und unterschiedliche Auswirkungen auf die Gestaltung des Erweiterungsbaus des Kunstmuseums und dessen unterirdischen Verbindungstrakt, zumindest in der Bauphase unterschiedliche Auswirkungen auf die Flüsse des öffentlichen und privaten Verkehrs, ferner unterschiedliche Kosten und Anforderungen an die Verlegung weiterer Infrastruktur (Tramschienen, Werkleitungskanäle), schliesslich auch unterschiedliche Auswirkungen auf die Aus- und Einfahrten der beiden Parkings, auf den Fussgängerverkehr und auf Zu- und Wegfahrten, auf die Störung des öffentlichen Verkehrs und die Anbindung an das öV-Netz sowie auf die Offenhaltung städtebaulicher Optionen. Dass diese Sachverhaltsfeststellungen offensichtlich unrichtig wären, macht die Beschwerdeführerin jedoch nicht geltend. Ob daraus gefolgert werden kann, es handle sich um einen Standortentscheid, ist wiederum eine Frage der rechtlichen Qualifikation und nicht der Sachverhaltsfeststellung (vgl. E. 6.3.1 hiernach).
5. Die Beschwerdeführerin rügt, entgegen der Auffassung der Vorinstanz seien die Verfahrensregeln des Vergaberechts anwendbar. Die Vorinstanz habe dies willkürlich verneint und damit das Übereinkommen vom 15. April 1994 über das öffentliche Beschaffungswesen (GPA; SR 0.632.231.422), Art. 1, 6 und 11 der Interkantonalen Vereinbarung vom 25. November 1994/15. März 2001 über das öffentliche Beschaffungswesen [IVöB; AS 2003 196 ff.] und Art. 5 Abs. 1 BGBM sowie Art. 9 BV verletzt.
5. Die Beschwerdeführerin rügt, entgegen der Auffassung der Vorinstanz seien die Verfahrensregeln des Vergaberechts anwendbar. Die Vorinstanz habe dies willkürlich verneint und damit das Übereinkommen vom 15. April 1994 über das öffentliche Beschaffungswesen (GPA; SR 0.632.231.422), Art. 1, 6 und 11 der Interkantonalen Vereinbarung vom 25. November 1994/15. März 2001 über das öffentliche Beschaffungswesen [IVöB; AS 2003 196 ff.] und Art. 5 Abs. 1 BGBM sowie Art. 9 BV verletzt.
5.1 5.1.1 Das GPA findet nach Art. I Abs. 1 Anwendung auf alle Gesetze, Vorschriften, Verfahren und Praktiken betreffend die öffentlichen Beschaffungen durch die dem Abkommen unterliegenden Stellen; dazu gehören gemäss Anhang I Annex 2 die kantonalen Behörden, mithin der Beschwerdegegner (vgl. auch Art. 8 Abs. 1 lit. a IVöB). In sachlicher Hinsicht findet es Anwendung auf jede Beschaffung durch vertragliche Methoden, einschliesslich Kauf oder Leasing, Miete oder Miete-Kauf, mit oder ohne Kaufoptionen (Art. I Abs. 2 GPA). Nach Art. 5 Abs. 1 BGBM richten sich die öffentlichen Beschaffungen durch Kantone, Gemeinden und andere Träger kantonaler oder kommunaler Aufgaben nach kantonalem oder interkantonalem Recht, wobei Personen mit Niederlassung oder Sitz in der Schweiz nicht in einer Weise benachteiligt werden dürfen, welche Art. 3 BGBM widerspricht. Eine nähere Definition des Begriffs "Beschaffung" enthalten weder das GPA noch das BGBM.
5.1.2 Nach Lehre und Rechtsprechung ist kennzeichnend für das Beschaffungsrecht, dass der Staat als Nachfrager Waren oder Dienstleistungen gegen eine Gegenleistung beschafft, um damit seine Aufgaben wahrzunehmen (BGE 125 I 209 E. 6b S. 213; 126 I 250 E. 2d/bb S. 255 f.; 128 I 136 E. 4.1 S. 146; 135 II 49 E. 4.3.2 S. 55 f.; MARTIN BEYELER, Der Geltungsanspruch des Vergaberechts, 2012, Rz. 604 und 620; GALLI/MOSER/LANG/CLERC, Praxis des öffentlichen Beschaffungsrechts, 2. Aufl. 2007, S. 45 Rz. 107; FRANÇOIS BELLANGER, La notion de "marché public", une définition sans concession? in: Les droits de l'homme et la constitution, 2007, S. 400 f., 407 f.; DANIEL KUNZ, Verfahren und Rechtsschutz bei der Vergabe von Konzessionen, 2004, S. 161, 166 f.; CASPAR ZELLWEGER/ANNATINA WIRZ, Das öffentliche Beschaffungsrecht des Kantons Basel-Stadt, in: Denise Buser [Hrsg.], Neues Handbuch des Staats- und Verwaltungsrechts des Kantons Basel-Stadt, 2008, S. 577; RHINOW/SCHMID/BIAGGINI/UHLMANN, Öffentliches Wirtschaftsrecht, 2. Aufl. 2011, § 19 Rz. 5).
Das Bundesgericht hat in BGE 125 I 209 E. 6b S. 214 sowie im Urteil 2P.19/2001 vom 16. Mai 2001 E. 1a/cc, in: RDAT 2001 II N. 96 S. 405, die Beschaffung der Ware oder Dienstleistung durch das Gemeinwesen mittels eines privatrechtlichen Vertrags als wesentliches Element der öffentlichen Beschaffung bezeichnet. Später hat es präzisiert, dass nicht bloss auf die Rechtsnatur des abgeschlossenen Vertrags, sondern auf eine funktionale Betrachtung abzustellen ist, damit die Anwendung des Vergaberechts nicht durch Wahl einer besonderen Rechtskonstruktion umgangen werden könne (BGE 135 II 49 E. 4.4 S. 56; vgl. auch die oben zitierten Literaturhinweise). Vorausgesetzt ist aber immer ein synallagmatisches Rechtsgeschäft, wobei der öffentliche Auftraggeber eine Leistung und der Leistungserbringer dafür eine Gegenleistung erhält (BELLANGER, a.a.O., S. 405; BEYELER, a.a.O., S. 290 ff.; KUNZ, a.a.O., S. 167). Ein solches im weiteren Sinne zu verstehendes Synallagma kann auch vorliegen, wenn der öffentliche Auftraggeber und Private gemeinsam eine Tätigkeit ausüben, bei welcher beide Seiten gewisse Leistungen erbringen und Gegenleistungen erhalten ("Public Private Partnership"; vgl. Urteil 2C_116/2007 vom 10. Oktober 2007 E. 4.4; BELLANGER, a.a.O., S. 418; BEYELER, a.a.O., S. 292 ff., 338, 467 ff.; MARTIN BEYELER, PPP auf dem Tischmacherhof: Grundsatzfragen und Vergaberecht, in: jusletter 7. Januar 2008, Rz. 43 ff.; URS BOLZ, Public Private Partnership (PPP) in der Schweiz, ZBl 105/2004 S. 573 f.). Voraussetzung für die Unterstellung unter das öffentliche Beschaffungsrecht ist aber auch hier, dass das Gemeinwesen als Nachfrager auftritt und die Leistung veranlasst, um eine öffentliche Aufgabe wahrzunehmen (BEYELER, a.a.O. [2012], S. 307 ff.; ZELLWEGER/WIRZ, a.a.O., S. 578 f.; JEAN-BAPTISTE ZUFFEREY/JULIEN LE FORT, L'assujettissement des PPP au droit des marchés publics, BR 2006 S. 101 f.).
5.1.3 Der blosse Umstand, dass der Staat einem Privaten erlaubt, eine bestimmte Tätigkeit auszuüben, ist keine öffentliche Beschaffung, weil der Staat dabei nicht eine Tätigkeit veranlasst oder ein Gut beschafft, sondern bloss eine private Tätigkeit hoheitlich ordnet oder reguliert (BGE 125 I 209 E. 6b S. 214 f.; BEYELER, a.a.O. [2012], S. 307 Rz. 670, S. 403 ff.). Dasselbe gilt grundsätzlich auch, wenn der Staat eine Sondernutzungskonzession für die Benützung öffentlichen Grundes erteilt, weil damit der Staat nicht etwas beschafft, sondern im Gegenteil dem Privaten ein Recht einräumt und dafür (in der Regel) eine Gegenleistung erhält (BGE 125 I 209 E. 6b S. 213; 128 I 136 E. 4.1 S. 146; 135 II 49 E. 4.3.2 S. 55 und E. 5.1 S. 57; BELLANGER, a.a.O., S. 417 f.; ETIENNE POLTIER, Les pouvoirs adjudicateurs, Champ d'application personnel du droit des marchés publics, AJP 2008 S. 1122; KUNZ, a.a.O., S. 169; MARCO FETZ, Öffentliches Beschaffungsrecht des Bundes, in: Allgemeines Aussenwirtschafts- und Binnenmarktrecht, SBVR Bd. XI, 2007, S. 511 Rz. 73; DANIEL KUNZ, Die Konzessionserteilung, in: Häner/Waldmann [Hrsg.], Die Konzession, 2011, S. 30; HANS RUDOLF TRÜEB/DANIEL ZIMMERLI, Keine Ausschreibungspflicht für Sondernutzungskonzessionen der Verteilnetzbetreiber, in: ZBl 112/2011 S. 134 f.; ZELLWEGER/WIRZ, a.a.O., S. 577 f.; THOMAS ZWALD, Das Bundesgesetz über den Binnenmarkt, in: Allgemeines Aussenwirtschafts- und Binnenmarktrecht, SBVR Bd. XI, 2007, S. 426 Rz. 59, S. 443 Rz. 126).
Anders verhält es sich nur, wenn mit der Erteilung der Konzession untrennbar Gegenleistungen von gewisser Bedeutung verbunden sind, die normalerweise Gegenstand einer öffentlichen Beschaffung bilden (BGE 135 II 49 E. 4.4 S. 56; BEYELER, a.a.O. [2012], S. 394 f., 402 f.; FETZ, a.a.O., S. 512 Rz. 75; KUNZ, a.a.O. [2011], S. 31 f.; TRÜEB/ZIMMERLI, a.a.O., S. 136). Eine solche mit einer Konzession verbundene Beschaffung hat das Bundesgericht in BGE 135 II 49 E. 5.2 angenommen, in dem das Gemeinwesen eine Sondernutzungskonzession erteilte und dies mit der Auflage, eine bestimmte Zahl von Leih-Fahrrädern der Öffentlichkeit zur Verfügung zu halten, verband. Entscheidend war hier, dass es in Wirklichkeit für das Gemeinwesen um eine öffentliche Aufgabe ging, welche mittels der Konzession und der damit verbundenen Auflage erfüllt werden sollte (BGE 135 II 49 E. 5.2.2; KUNZ, a.a.O. [2011], S. 31 f.).
Anders verhält es sich nur, wenn mit der Erteilung der Konzession untrennbar Gegenleistungen von gewisser Bedeutung verbunden sind, die normalerweise Gegenstand einer öffentlichen Beschaffung bilden (BGE 135 II 49 E. 4.4 S. 56; BEYELER, a.a.O. [2012], S. 394 f., 402 f.; FETZ, a.a.O., S. 512 Rz. 75; KUNZ, a.a.O. [2011], S. 31 f.; TRÜEB/ZIMMERLI, a.a.O., S. 136). Eine solche mit einer Konzession verbundene Beschaffung hat das Bundesgericht in BGE 135 II 49 E. 5.2 angenommen, in dem das Gemeinwesen eine Sondernutzungskonzession erteilte und dies mit der Auflage, eine bestimmte Zahl von Leih-Fahrrädern der Öffentlichkeit zur Verfügung zu halten, verband. Entscheidend war hier, dass es in Wirklichkeit für das Gemeinwesen um eine öffentliche Aufgabe ging, welche mittels der Konzession und der damit verbundenen Auflage erfüllt werden sollte (BGE 135 II 49 E. 5.2.2; KUNZ, a.a.O. [2011], S. 31 f.).
5.2 5.2.1 Vorliegend hat die Vorinstanz die Anwendbarkeit des öffentlichen Beschaffungsrechts "aufgrund der Natur der vom Privaten zu erfüllenden Aufgabe" verneint. Dies wird von der Beschwerdeführerin kritisiert: Es gehe um eine Bau- oder Dienstleistungskonzession, die als öffentliche Beschaffung zu qualifizieren sei; die Realisierung des Parkings liege im öffentlichen Interesse und sei deshalb vom Regierungsrat gefördert worden. Der Staat sei von Anfang an als geschäftsinteressierter Teilnehmer am Markt aufgetreten und habe Leistungen für Dritte (Parkplatzbenutzer) aktiv erhältlich gemacht. Der Beschwerdegegner habe das gesamte Projekt zur Verfolgung öffentlicher Aufgaben in Angriff genommen und trete nicht nur als hoheitlich oder vertraglich handelndes Ordnungssubjekt auf, sondern es gehe ihm darum, eine städtebauliche Lösung für den Verkehr in der Innenstadt zu entwickeln. Das sei eine öffentliche Aufgabe.
5.2.2 Im EU-Recht gelten als öffentliche Baukonzessionen, die dem Vergaberecht unterstehen, "Verträge, die von öffentlichen Bauaufträgen nur insoweit abweichen, als die Gegenleistung für die Bauleistungen ausschliesslich in dem Recht zur Nutzung des Bauwerks oder in diesem Recht zuzüglich der Zahlung eines Preises besteht" (Art. 1 Abs. 3 der Richtlinie 2004/18/EG des Europäischen Parlaments und des Rates vom 31. März 2004 über die Koordinierung der Verfahren zur Vergabe öffentlicher Bauaufträge, Lieferungen und Dienstleistungsaufträge [im Folgenden: VKR]; vgl. BELLANGER, a.a.O., S. 411 ff.; BEYELER, a.a.O. [2012], S. 405 ff.). Wesentlich daran ist, dass der Auftraggeber nicht nur eine private Tätigkeit reguliert, sondern den Partner beauftragt, eine öffentliche Aufgabe zu erfüllen, die sonst der Staat erfüllen würde (BEYELER, a.a.O. [2012], S. 414 f.; EVELYNE CLERC, in: Commentaire romand, Droit de la concurrence, 2002, N. 49 zu Art. 5 BGBM; ALEXANDER EGGER, Europäisches Vergaberecht, 2008, S. 202 Rz. 787).
5.2.3 Die Errichtung eines Parkhauses gehört nicht zu den Tätigkeiten, die gemäss Anhang I Annex 5 GPA bzw. Art. 3 des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft und der Europäischen Gemeinschaft über bestimmte Aspekte des öffentlichen Beschaffungswesens (SR 0.172.052.68) ungeachtet der Trägerschaft dem Vergaberecht unterstehen. Sie kann auch nicht ihrer Natur nach als staatliche oder öffentliche Aufgabe betrachtet werden: Der Staat kann selber als Bauherr ein Parkhaus errichten; in diesem Fall unterliegt er dem öffentlichen Beschaffungsrecht. Parkhäuser können aber auch von Privaten errichtet werden; ihre Erstellung unterliegt dann wie jede andere private Baute den bau- und planungsrechtlichen Anforderungen, was sie aber nicht zu einer öffentlichen Aufgabe macht und dem Vergaberecht unterstellt. Abgesehen von den staatlichen Kernaufgaben steht der Begriff der öffentlichen Aufgabe nicht wesensgemäss fest (BGE 125 I 209 E. 6b S. 213): Öffentliche Aufgabe ist grundsätzlich, was sich der Staat gesetzlich als Aufgabe gibt (BEYELER, a.a.O. [2012], S. 312 f.; Urteil 2C_485/2010 vom 3. Juli 2012 E. 8.3-8.5, zur Publikation vorgesehen). Aufgrund des Legalitätsprinzips (Art. 5 Abs. 1 BV), welches für das ganze Verwaltungshandeln mit Einschluss der Leistungsverwaltung gilt (BGE 103 Ia 369 E. 5 und 6 S. 380 ff.; 123 I 1 E. 2b S. 3 f.; 130 I 1 E. 3.1 S. 5), bedürfte der Staat einer entsprechenden gesetzlichen Grundlage, um selber ein Parkhaus zu errichten. Vorliegend ist weder von der Vorinstanz festgestellt noch von der Beschwerdeführerin behauptet worden, der Kanton sei gesetzlich verpflichtet oder auch nur ermächtigt, ein Parkhaus zu erstellen. Mangels einer gesetzlichen Grundlage ist der Bau des umstrittenen Parkhauses daher nicht eine staatliche, sondern eine private Aufgabe.
5.2.4 Die Vorinstanz hat zwar in E. 2.1 des angefochtenen Entscheids die Frage aufgeworfen, ob auf die Vergabe von öffentlichem Grund an eine private Trägerschaft im Rahmen einer Public Private Partnership die Verfahrensregeln des Beschaffungsrechts zur Anwendung kommen. Sie hat jedoch nicht festgestellt, dass sich der Kanton am vorgesehenen Parking finanziell beteiligen oder er eine private Projektträgerschaft mit dem Bau und Betrieb des Parkings beauftragen würde; dies wird auch von der Beschwerdeführerin nicht behauptet. Nach den Feststellungen der Vorinstanz entstand das Projekt vielmehr aus privater Initiative und die Mitwirkung des Kantons beschränkte sich darauf, die notwendigen Rechtsgrundlagen zu schaffen, d.h. einerseits der privaten Bauherrschaft die Nutzung des öffentlichen Grundes für die Realisierung des Parkings zu erlauben und andererseits einen Bebauungsplan zu erlassen. Etwas anderes ergibt sich auch nicht aus dem von der Beschwerdeführerin zitierten Regierungsratsbeschluss vom 9. Januar 2007. Dass der Kanton gemäss Schreiben des Hochbau- und Planungsamtes vom 2. Juni 2008 eine Wirtschaftlichkeitsrechnung für die Projekte verlangte und diese in den Variantenvergleich einbezog, steht im Zusammenhang mit dem Landeigentümerrisiko im Hinblick auf die Entrichtung des Baurechtszinses. Sodann ist das Vorgehen, für die Zurverfügungstellung öffentlichen Grundes an einen Privaten einen Baurechtszins zu verlangen, üblich und stellt weder eine wirtschaftliche Beteiligung des Kantons an der projektierten Anlage dar noch führt es dazu, dass diese zu einer öffentlichen Aufgabe würde (vgl. E. 5.1.3 hiervor).
5.2.5 Daran ändert auch nichts, dass der Kanton im Zusammenhang mit der Realisierung des Parkings eine städtebauliche Lösung gesucht hat und beabsichtigt, für die Errichtung der Baute einen Bebauungsplan zu erlassen. Ein Bebauungsplan ist ein Instrument, um für begrenzte Gebiete eine bessere Bebauung zu gewährleisten als die baurechtliche Grundordnung (§ 101 des Bau- und Planungsgesetzes [des Kantons Basel-Stadt] vom 17. November 1999 [BPG/BS; SG 730.100]; vgl. dazu VERA FELDGES/CAROLINE BARTHE, Raumplanungs- und Baurecht, in: Buser, a.a.O., S. 785 f.). Es ist raumplanungsrechtlich vorgegeben, dass der Staat bei seiner Planung - mithin auch beim Erlass eines Bebauungsplans - die räumlichen und umweltbezogenen Auswirkungen des Projekts prüft und zu optimieren versucht (vgl. Art. 3 RPG [SR 700]). Dadurch wird aber der Erlass des Bebauungsplans oder die darauf gestützte Erstellung einer Baute nicht zu einer öffentlichen Aufgabe, für welche das Vergaberecht Anwendung fände. Der Kanton handelt dabei vielmehr als hoheitlicher Regulator einer privaten Tätigkeit. Auch der Umstand, dass der private Bauherr für die Realisierung der Baute öffentlichen Grund beansprucht, was ihm durch eine Sondernutzungskonzession oder einen Baurechtsvertrag erlaubt wird, macht die Realisierung der Baute nicht zu einer öffentlichen Aufgabe. Es liegt auch keine mit der Konzession verbundene Auflage oder Gegenleistung im Sinne der dargelegten Rechtsprechung (BGE 135 II 49; vgl. E. 5.1.3 hiervor) vor: Sowohl die Sondernutzungskonzession als auch der Bebauungsplan geben dem Privaten das Recht, die betreffende Anlage zu errichten, verpflichten ihn aber nicht zu einer öffentlichen Aufgabe.
5.3 Insgesamt fällt die Planung und Errichtung des hier zur Diskussion stehenden Parkhauses somit nicht in den Anwendungsbereich des öffentlichen Beschaffungsrechts im Sinne des massgeblichen Staatsvertragsrechts. Im Übrigen wird von der Beschwerdeführerin auch nicht in rechtsgenüglicher Weise (vgl. Art. 106 Abs. 2 BGG) dargelegt, dass das kantonale oder interkantonale Recht einen weiteren Begriff des öffentlichen Beschaffungsrechts kennen würde. Damit ist auch Art. 5 Abs. 1 BGBM nicht verletzt, der seinerseits auf das kantonale oder interkantonale Recht verweist. Die Vorinstanz hat daher im angefochtenen Entscheid mit Recht die direkte Anwendbarkeit des öffentlichen Beschaffungsrechts verneint.
6. Die Beschwerdeführerin rügt sodann, die Vorinstanz habe ohne nähere Begründung und willkürlich offen gelassen, ob Art. 2 Abs. 7 BGBM anwendbar sei und dadurch diese Bestimmung verletzt. Weiter seien auch die Wirtschaftsfreiheit bzw. der darin enthaltene Grundsatz der Gleichbehandlung der Gewerbegenossen sowie die Rechtsschutzmöglichkeiten nach Art. 9 Abs. 1 und 2 BGBM und damit auch Art. 29 Abs. 1 BV verletzt.
6.1 Worin die Verletzung der Wirtschaftsfreiheit liegen soll, wird von der Beschwerdeführerin nicht rechtsgenüglich dargelegt (vgl. Art. 106 Abs. 2 BGG), so dass darauf nicht näher einzugehen ist.
6.2 Nach Art. 2 Abs. 7 BGBM muss die Übertragung der Nutzung kantonaler und kommunaler Monopole auf Private auf dem Weg der Ausschreibung erfolgen und darf Personen mit Niederlassung oder Sitz in der Schweiz nicht diskriminieren. Beschränkungen dieses Rechts sind in Form einer anfechtbaren Verfügung zu erlassen und unterliegen einem Rechtsmittel an mindestens eine verwaltungsunabhängige Behörde (Art. 9 Abs. 1 und 2 BGBM).
Unabhängig von der von der Vorinstanz offen gelassenen Frage, ob Art. 2 Abs. 7 BGBM auf die hier zur Diskussion stehende Sondernutzungskonzession überhaupt anwendbar ist, ist zu bemerken, dass das Erfordernis der Ausschreibung primär auf Konstellationen zugeschnitten ist, in denen das Gemeinwesen aus eigenem Antrieb eine solche Übertragung von Monopolen vornehmen will. Nach den vorinstanzlichen Sachverhaltsfeststellungen (vgl. E. 5.2.4 hiervor) hat jedoch die Beschwerdeführerin aus eigener Initiative an dem Parking-Projekt zu arbeiten begonnen und ist - ebenso wie ihre Konkurrentinnen - erst später an den Kanton gelangt. Im Anschluss an diese private Initiative haben sich die kantonalen Behörden bereit erklärt, für eines der Projekte eine Sondernutzungskonzession zu erteilen, ohne dass sie zuvor eine Ausschreibung durchgeführt hätten. Die Beschwerdeführerin war damit von Anfang an federführend im Verfahren involviert und es ist nicht ersichtlich, inwiefern sie an der nachträglichen Durchführung eines Ausschreibungsverfahrens ein schutzwürdiges Interesse haben könnte. Fraglich kann hier somit nur noch sein, ob der Regierungsrat verpflichtet gewesen wäre, seinen Variantenentscheid in Form einer anfechtbaren Verfügung zu eröffnen.
6.3 Entgegen der Darstellung der Beschwerdeführerin hat die Vorinstanz nicht ohne Begründung die Frage der Anwendbarkeit von Art. 2 Abs. 7 BGBM offen gelassen. Sie hat vielmehr einlässlich begründet, dass noch gar kein rechtsverbindlicher Entscheid vorliege, sondern es erst um die Vorbereitung eines Entscheids gehe, der dem Grossen Rat und allenfalls dem Volk obliege. Diese Begründung ist entgegen der Auffassung der Beschwerdeführerin weder willkürlich noch rechtswidrig:
6.3.1 Die Beschwerdeführerin macht geltend, es gehe entgegen der Auffassung der Vorinstanz nicht um einen raumplanerischen bzw. Standortentscheid, sondern um eine Sondernutzungskonzession und dabei um die Auswahl zwischen zwei Projekten, wobei dem obsiegenden Projektträger das Sondernutzungsrecht erteilt und mit ihm ein entsprechender Vertrag abgeschlossen werden soll. Das Treffen eines raumplanerischen Standortentscheids und die Erteilung einer Sondernutzungskonzession schliessen sich aber gegenseitig nicht aus: Es ist typisch für grössere Bauvorhaben, zumal in städtischen Gebieten, dass sie gleichzeitig öffentlichen Grund beanspruchen und Auswirkungen zeitigen, die raumplanungsrechtlich relevant sind. Die Beschwerdeführerin stellt nicht in Frage, dass es zumindest auch um einen Standortentscheid geht, befinden sich doch die Projekte an verschiedenen Standorten. Nach dem vorinstanzlich verbindlich festgestellten Sachverhalt (vgl. E. 4.3 hiervor) hat die Variantenwahl zwischen den beiden Projekten jedenfalls gewisse planerische Auswirkungen. Raumplanerische Entscheide umfassen nicht nur die Standorte, sondern auch die planungswirksamen Auswirkungen der zu planenden Anlagen (vgl. Art. 3 Abs. 3 RPG). Bei dem zu treffenden Entscheid geht es somit zumindest auch um einen raumplanerischen Entscheid. Die Beschwerdeführerin stellt denn auch die Auffassung der Vorinstanz nicht in Frage, wonach die Realisierung des Projekts nach kantonalem Recht eines Bebauungsplans bedürfe (vgl. Art. 106 Abs. 2 BGG).
6.3.2 Ebenso wenig stellt die Beschwerdeführerin in Frage, dass nach kantonalem Recht sowohl für die Erteilung der Sondernutzungskonzession als auch für den Erlass des Bebauungsplans der Grosse Rat zuständig ist und die Beschwerdeführerin gegen dessen Entscheide Rechtsmittel ergreifen kann. Bei dieser Ausgangslage trifft die Auffassung der Vorinstanz zu, dass die bisherige Evaluationstätigkeit des Regierungsrates bzw. des BVD noch nicht in rechtsverbindliche Entscheide gemündet hat, sondern erst vorbereitende Handlungen im Hinblick auf den vom Grossen Rat zu treffenden Entscheid vorliegen. Sodann ist es ein allgemeiner Grundsatz der Verwaltungsrechtspflege, dass nur rechtsverbindliche Entscheide anfechtbar sind, nicht dagegen blosse Vorbereitungshandlungen oder Anträge (vgl. BGE 136 I 323 E. 4.4 mit Hinweisen; Urteil 2C_272/2012 vom 9. Juli 2012 E. 5.1).
6.3.3 Zwar ist die Darstellung der Beschwerdeführerin, wonach das BVD nicht bloss Standorte bewertet, sondern konkrete Projekte miteinander verglichen hat, zutreffend. Davon geht aber auch die Vorinstanz aus, wenn sie ausführt, der Regierungsrat habe im Rahmen seiner Vorbereitung für den Bebauungsplan einen Variantenentscheid getroffen. Das ändert aber nichts an der für die Vorinstanz entscheiderheblichen Auffassung, dass noch kein rechtsverbindlicher Entscheid vorliegt und dass das entscheidkompetente Organ (Grosser Rat bzw. Stimmbevölkerung) ohnehin nicht an den Variantenentscheid des Regierungsrates gebunden ist. Nicht entscheidend ist sodann, dass das BVD vom Regierungsrat beauftragt wurde, einen Entwurf zu einem Baurechtsvertrag auszuarbeiten; ein entsprechender Vertrag könnte rechtsverbindlich erst nach dem Beschluss des Grossen Rates abgeschlossen werden.
6.3.4 Die Beschwerdeführerin bringt allerdings vor, durch die vom Regierungsrat getroffene Auswahl des privaten Partners bzw. Projekts werde die Sondernutzungskonzession präjudiziert, weshalb bereits der Variantenentscheid des Regierungsrates in Form einer anfechtbaren Verfügung zu ergehen habe. Sie geht offenbar davon aus, dass sie den abschliessenden Entscheid des Grossen Rates nicht mehr anfechten oder zumindest dannzumal die Variantenwahl nicht mehr zur Diskussion stellen könne. Sie begründet diese Auffassung jedoch nicht. Nach § 105 BPG/BS beschliesst der Grosse Rat über Bebauungspläne. Ist das Parlament nicht bloss Genehmigungs-, sondern Beschlussinstanz, entspricht es allgemeinen Grundsätzen, dass die Regierung zwar dem Parlament Anträge stellen kann, dieses aber nicht bloss die Anträge annehmen oder ablehnen, sondern sie auch inhaltlich ändern kann. Sodann ist nach § 113 Abs. 2 BPG/BS auch der Planungsbeschluss des Grossen Rates mit Rekurs beim Verwaltungsgericht anfechtbar (vgl. FELDGES/BARTHE, a.a.O., S. 790 ff.), was sich im Übrigen bereits aus dem Bundesrecht ergibt (Art. 33 f. RPG i.V.m. Art. 86 Abs. 2 BGG). Die Beschwerdeführerin wird dabei rekursweise vorbringen können, das Verfahren unterstehe den Anforderungen von Art. 2 Abs. 7 BGBM und diese seien im Verfahren missachtet worden.
6.4 Liegt somit noch kein rechtsverbindlicher, anfechtbarer Entscheid vor, hat die Vorinstanz keine Rechtsverletzung begangen, indem sie die Frage der Anwendbarkeit von Art. 2 Abs. 7 BGBM offen gelassen hat. Damit sind auch Art. 9 BGBM bzw. Art. 29 Abs. 1 BV nicht verletzt.
7. Die Beschwerdeführerin rügt schliesslich, die Vorinstanz habe die Koordinationspflicht (Art. 25a RPG) verletzt, indem sie willkürlich davon ausgegangen sei, es gehe nicht um die Erteilung einer Sondernutzungskonzession. Entgegen dieser Darstellung ist aber die Vorinstanz nicht davon ausgegangen, es gehe nicht um eine Sondernutzungskonzession; entscheidend für sie war, dass noch kein rechtsverbindlicher Entscheid vorliegt, der angefochten werden könnte, was - wie soeben ausgeführt (vgl. E. 6.3 hiervor) - zutrifft. Eine allfällige Verletzung der Koordinationspflicht kann im Anschluss an einen rechtsverbindlichen Planungsentscheid gerügt werden (vgl. Art. 33 Abs. 4 RPG).
8. Unter diesen Umständen hat die Vorinstanz zu Recht erkannt, dass bisher kein anfechtbarer Entscheid vorliegt und der Beschwerdegegner auch nicht verpflichtet gewesen wäre, seinen bisherigen Vorentscheid in eine solche Form zu kleiden. Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen.
Bei diesem Ausgang des Verfahrens trägt die Beschwerdeführerin die Kosten des bundesgerichtlichen Verfahrens (Art. 66 Abs. 1 BGG). Der obsiegende Kanton hat keinen Anspruch auf Parteientschädigung (Art. 68 Abs. 3 BGG). Die weitere Beteiligte Y._ AG hat auf eine Stellungnahme verzichtet und ebenfalls keinen Anspruch auf Parteikostenersatz.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Die Gerichtskosten von Fr. 5'000.-- werden der Beschwerdeführerin auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht schriftlich mitgeteilt.
Lausanne, 16. Oktober 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger