Sachverhalt:
A. X._ benötigte dringend Geld zur Begleichung privater Schulden. Nachdem er Heroin, Kokain und vermutlich auch Alkohol konsumiert hatte, begab er sich am 31. Oktober 2007 um ca. 23 Uhr zum Hotel A._. Dort stülpte er sich eine Stoffmütze mit Sehschlitzen über und nahm den mitgebrachten Revolver zur Hand. Im Hotelinnern drängte er sich bei der Rezeption hinter den Tresen zur Hotelangestellten B._, welche er mit vorgehaltener, schussbereiter Waffe erfolgreich zur Herausgabe von Geld anhielt. Dieses verstaute X._ zusammen mit dem Revolver in einer Plastiktasche. Auf dem Weg zum Hotelausgang wurde er vom Nachtportier Y._ verfolgt und von hinten festgehalten. X._ gelang es, sich aus der Umklammerung zu befreien. Der Nachtportier stiess ihn gegen die gläsernen Ausgangstüren des Hotels und riss ihm die Mütze vom Kopf. Bei einem erneuten Fluchtversuch X._s hielt ihn der Nachtportier - nunmehr im Aussenbereich des Hotels - erneut von hinten fest. Die beiden Kämpfenden gingen zu Boden. X._ drohte dem Nachtportier, ihn zu erschiessen, falls er nicht loslasse. Es gelang ihm, den in der Plastiktasche verstauten Revolver zu behändigen und diesen gegen seinen Widersacher bzw. dessen Kopf zu richten, welcher versuchte, die Hände X._s bzw. die auf ihn gerichtete Waffe wegzudrücken. Als ihn die Kräfte verliessen, stiess er X._ gegen eine im Aussenbereich des Hotels stehende Betonsäule und ergriff die Flucht. Unmittelbar darauf löste sich aus dem Revolver X._s ein Schuss, der hinter dem fliehenden Nachtportier auf den Boden prallte und anschliessend in die Schaufensterauslage eines Elektrofachgeschäfts einschlug.
B. Das Strafgericht Basel-Stadt erkannte X._ mit Urteil vom 17. Juni 2009 anklagegemäss schuldig des versuchten Mords, des qualifizierten Raubs, der Sachbeschädigung, des Konsums von Betäubungsmitteln und der Widerhandlung gegen das Waffengesetz. Es bestrafte ihn mit 11 Jahren Freiheitsstrafe und einer Busse von 100 Franken (Ersatzfreiheitsstrafe 1 Tag). Es verpflichtete X._, Y._ eine Genugtuung von Fr. 12'000.-- zu zahlen, und hiess dessen Schadenersatzforderung dem Grundsatz nach gut. Bezüglich der Höhe des Schadens und der Mehrforderung von Fr. 3'000.-- betreffend die Genugtuung verwies es Y._ auf den Zivilweg.
C. Auf Appellation von X._ hin bestätigte das Appellationsgericht des Kantons Basel-Stadt am 19. Januar 2011 das erstinstanzliche Urteil unter Anrechnung der bisher ausgestandenen Haft.
D. Mit Beschwerde in Strafsachen beantragt X._ die Aufhebung des Urteils des Appellationsgerichts und die Rückweisung der Sache an die Vorinstanz zur Neubeurteilung. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
E. Das Appellationsgericht des Kantons Basel-Stadt, die Staatsanwaltschaft des Kantons Basel-Stadt sowie Y._ beantragen die Abweisung der Beschwerde.

Erwägungen:
1. Der Beschwerdeführer ficht den Schuldspruch des versuchten Mords gemäss <ref-law> i.V.m. <ref-law> unter Berufung auf den Grundsatz "in dubio pro reo", das Willkürverbot und den Anklagegrundsatz unter Einschluss des Gehörrechts und des Anspruchs auf ein faires Verfahren als verfassungswidrig an.
2. Gemäss dem in <ref-law> und in Art. 6 Ziff. 2 EMRK verankerten Grundsatz "in dubio pro reo" ist bis zum gesetzlichen Nachweis der Schuld zu vermuten, dass der wegen einer strafbaren Handlung Angeklagte unschuldig ist. Als Beweiswürdigungsregel besagt die Maxime, dass sich der Strafrichter nicht von der Existenz eines für den Angeklagten ungünstigen Sachverhalts überzeugt erklären darf, wenn bei objektiver Betrachtung erhebliche und nicht zu unterdrückende Zweifel bestehen, ob sich der Sachverhalt so verwirklicht hat (<ref-ruling> E. 2a S. 41).
2.1 Im Rahmen der Beweiswürdigung hält die Vorinstanz im angefochtenen Urteil zusammenfassend fest, dass es zwischen dem Beschwerdeführer und dem Beschwerdegegner im Eingangs/Ausgangsbereich des Hotels A._ zu einem Kampf gekommen war, in dessen Verlaufe der Beschwerdeführer Todesdrohungen ausstiess und es ihm gelang, die in der mitgeführten Plastiktasche verstaute Waffe hervorzuholen und auf den Beschwerdegegner bzw. dessen Kopf zu richten. Hingegen kann nach der Auffassung der Vorinstanz entgegen den Erwägungen im erstinstanzlichen Urteil in tatsächlicher Hinsicht nicht festgestellt werden, ob der Schlaghammer des Revolvers vorgespannt war oder nicht. Die Vorinstanz geht in Bezug auf den Anklagevorwurf des versuchten Mords daher von zwei möglichen Tatvarianten aus: Einerseits legt sie dem Beschwerdeführer - ausgehend davon, dass der Schlaghammer nicht gespannt war und ein Abzugsgewicht von 6,5 kg überwunden werden musste - eine gezielte und absichtliche Schussabgabe in Richtung des fliehenden Beschwerdegegners zur Last. Dass der Beschwerdeführer den Beschwerdegegner nicht getroffen habe, sei reines Glück, nicht aber dessen Können oder Absicht zuzuschreiben (angefochtenes Urteil, S. 10 f. Ziff. 4.1). Andererseits schliesst die Vorinstanz - soweit sie in tatsächlicher Hinsicht von einem gespannten Schlaghammer und damit von einem Abzugsgewicht von nur 1,5 kg ausgeht - die Möglichkeit nicht aus, dass sich der Schuss während bzw. unmittelbar nach dem Handgemenge unbeabsichtigt löste. Insoweit sei dem Beschwerdeführer vorzuwerfen, dass er eine geladene und ungesicherte Waffe in den Zweikampf eingeführt und dabei mehrfach gegen den Kopf seines Widersachers gerichtet habe (angefochtenes Urteil, S. 11 Ziff. 4.2).
2.2 Die Vorinstanz geht von zwei Tatvarianten aus, weil sich das Geschehen betreffend die Schussabgabe beweismässig nicht zweifelsfrei erstellen lässt. Eine gezielte Schussabgabe in Richtung des Fliehenden wird ebenso für möglich erachtet wie das im Handgemenge unbeabsichtigte Auslösen eines Schusses. Wie das Bundesgericht in konstanter Rechtsprechung bereits in <ref-ruling> E. 2c festgehalten hat, ist für den Fall, dass die Klärung bestimmter Tatsachen im Einzelfall scheitert bzw. der Ablauf eines tatsächlichen Geschehens zweifelhaft ist, nach dem Grundsatz "in dubio pro reo" zu entscheiden (siehe <ref-ruling> E. 2a, 124 IV 86 E. 2a S. 88, 120 Ia 31 E. 2c S. 35; siehe zum Grundsatz "in dubio pro reo" auch ESTHER TOPHINKE, Basler Kommentar, Schweizerische Strafprozessordnung, Basel 2011, Art. 10 Rz. 76, NIKLAUS SCHMID, Strafprozessrecht, 4. Aufl., Zürich 2004, § 17 Rz. 294). Werden wie hier von der Vorinstanz zwei Tatvarianten für möglich gehalten, nämlich eine günstige und eine ungünstige, bringt das Gericht damit selber zum Ausdruck, dass es von der ungünstigen Variante nicht überzeugt ist. Dies hat in Anwendung der Maxime "in dubio pro reo" als Entscheidregel zur Folge, dass es von der für den Angeschuldigten günstigen bzw. günstigeren Sachverhaltsannahme ausgehen muss. Indem die Vorinstanz bei der Fallbeurteilung beide Sachverhaltsvarianten, also auch die für den Beschwerdeführer ungünstige Variante, beibehielt, verletzte sie den Grundsatz "in dubio pro reo". Der Beurteilung des Falles ist richtiger Ansicht nach einzig die günstige Annahme zugrunde zu legen, nämlich diejenige, wonach sich ein Schuss im bzw. unmittelbar nach dem Handgemenge mit dem Beschwerdegegner unbeabsichtigt löste (Beschwerde, S. 9). Die Frage, ob die für den Beschwerdeführer ungünstigere Variante der gezielten, gewollten und bewussten Schussabgabe vor dem Willkürverbot standhielte, falls der Richter von ihr überzeugt gewesen wäre und sie daher angenommen hätte, stellt sich unter diesen Umständen nicht. Auf die entsprechenden Ausführungen in der Beschwerde (S. 5-8) braucht nicht eingegangen zu werden.
3. Nach dem aus Art. 29 Abs. 2 und Art. 32 Abs. 2 BV sowie aus Art. 6 Ziff. 1 und Ziff. 3 lit. a und b EMRK abgeleiteten Anklagegrundsatz bestimmt die Anklageschrift den Gegenstand des Gerichtsverfahrens (Umgrenzungsfunktion). Die Anklage hat die dem Angeklagten zur Last gelegten Delikte in ihrem Sachverhalt so präzise zu umschreiben, dass die Vorwürfe genügend konkretisiert sind. Das Anklageprinzip gewährleistet zugleich die Verteidigungsrechte und das Gehörsrecht des Angeklagten (Informationsfunktion). Dieser muss aus der Anklage ersehen können, wessen er angeklagt ist. Das bedingt eine zureichende Umschreibung der Tat. Entscheidend ist, dass der Angeklagte genau weiss, welcher konkreter Handlungen er beschuldigt und wie sein Verhalten rechtlich qualifiziert wird, so dass er sich in seiner Verteidigung richtig vorbereiten kann. Er darf nicht Gefahr laufen, erst an der Gerichtsverhandlung mit neuen Anschuldigungen konfrontiert zu werden (<ref-ruling> E. 2a, 120 IV 348 E. 2c; s.a. <ref-ruling>; <ref-ruling> E. 1b und d; <ref-ruling>; vgl. NIKLAUS OBERHOLZER, Grundzüge des Strafprozessrechts, Bern 2005, 2. Aufl., S. 317 Rz. 728). Besondere Fragen stellen sich im Hinblick auf die Gewährung des rechtlichen Gehörs und die Verteidigungsrechte, wenn das Gericht eine andere rechtliche Qualifizierung des eingeklagten Sachverhalts vornimmt (siehe Urteil 6B_225/2008 vom 7. Oktober 2008 E. 1.1, publiziert in sic! 3/2009 154; zum Ganzen MARCEL ALEXANDER NIGGLI/STEFAN HEIMGARTNER, Basler Kommentar, Schweizerische Strafprozessordnung, Basel 2011, Art. 9 und Art. 350 StPO).
3.1 Die Staatsanwaltschaft des Kantons Basel-Stadt klagte den Beschwerdeführer formell u.a. wegen versuchten Mords an. Er habe nach dem Gerangel bewusst und in der Absicht bzw. unter Inkaufnahme des Tötungserfolgs in skrupelloser Weise gezielt auf den fliehenden Beschwerdegegner geschossen, wobei das Geschoss nicht gemäss Absicht des Angeklagten den um sein Leben rennenden Beschwerdegegner traf, sondern in dessen unmittelbarer Nähe auf den Boden prallte und in der Folge in das Schaufenster eines Elektrofachgeschäfts einschlug. Gestützt auf diesen Anklagesachverhalt der bewussten und gewollten Schussabgabe in Richtung des fliehenden Beschwerdegegners sprach die erste Instanz den Beschwerdeführer wegen versuchten eventualvorsätzlichen Mords schuldig (erstinstanzliches Urteil, S. 28). Demgegenüber sieht die Vorinstanz die versuchte Tötung bzw. den versuchten Mord auch - und worauf in Anwendung des Grundsatzes "in dubio pro reo" einzig abzustellen ist - im Umstand, dass der Beschwerdeführer die ungesicherte und geladene Waffe behändigte und in das Handgemenge mit dem Beschwerdegegner einbrachte. Unter Hinweis auf <ref-ruling> führt sie aus, dem Beschwerdeführer sei das Wissen anzulasten, dass sich im Verlaufe des Handgemenges unerwartet ein Schuss hätte lösen und einen der Kämpfenden tödlich hätte treffen können. Namentlich aufgrund seiner gegenüber dem Beschwerdegegner ausgestossenen Drohungen, ihn zu töten, sei davon auszugehen, dass der Beschwerdeführer eine derartige tödliche Schussabgabe zumindest billigend in Kauf genommen habe (angefochtenes Urteil, S. 10).
3.2 In der Anklageschrift wird das Gerangel zwischen dem Beschwerdeführer und dem Beschwerdegegner, in dessen Verlaufe jener die geladene und entsicherte Waffe aus der Plastiktasche hervorholte und gegen seinen Widersacher bzw. dessen Kopf richtete, als Teil des Geschehens im Handlungsablauf umschrieben (kantonale Akten, act. 707, Ziff. 3). Ebenso werden in der Anklageschrift die Einwendungen des Beschwerdeführers wiedergegeben, mit welcher er sich gegen die Mordanklage wegen der ihm formell zur Last gelegten, gezielten und gewollten Schussabgabe zur Wehr setzt. So will er nicht vorsätzlich oder gezielt auf den Beschwerdegegner geschossen haben, sondern hat sich der Schuss beim Hantieren mit der Waffe ohne seinen Willen im bzw. nach dem Gerangel mit dem Beschwerdegegner unbeabsichtigt gelöst (kantonale Akten, act. 708, Ziff. 4). Damit wird die von der Vorinstanz der Beurteilung des Falles (ebenfalls) zugrunde gelegte Sachverhaltsvariante in der Anklageschrift - insbesondere unter Bezugnahme auf die Verteidigungsstrategie des Beschwerdeführers - zwar erwähnt, diesem (bloss) dadurch allerdings weder in tatsächlicher noch rechtlicher Hinsicht in der Anklage strafrechtlich formell zur Last gelegt. In der Anklageschrift ist insoweit denn auch mit keinem Wort dargestellt, dass und weshalb der Beschwerdeführer beim erwähnten Einbringen der Waffe in das Handgemenge in Kauf genommen haben soll, dass sich ein tödlicher Schuss lösen könnte. Die Anklage erwähnt zwar wohl die vom Beschwerdeführer ausgestossenen Todesdrohungen, doch zieht sie daraus - mit Recht - nicht den Schluss auf Inkaufnahme eines allfälligen Tötungserfolgs (kantonale Akten, act. 707, Ziff. 3). Ebenso wenig wird in der Anklageschrift thematisiert, welches denn die tatsächlichen Voraussetzungen sein sollen, die in diesem Zusammenhang auf eine Mordqualifikation schliessen lassen würden. Die Anklageschrift wirft dem Beschwerdeführer mithin nicht vor, er habe in Kauf genommen, dass sich aus der ins Gerangel eingebrachten Schusswaffe ein tödlicher Schuss lösen könnte, und sich (auch) bei dieser Variante eines eventualvorsätzlichen Versuchs eines Tötungsdelikts, gar eines Mords, schuldig gemacht. Indem die Vorinstanz bei der von ihr (ebenfalls) angenommenen günstigen - und deshalb ausschliesslich massgebenden - Sachverhaltsvariante aber genau hievon ausgeht, beurteilt sie im angefochtenen Urteil einen Sachverhalt, der nicht formell eingeklagt ist. Sie verletzt dadurch den Anklagegrundsatz.
3.3 Das angefochtene Urteil erweist sich aus einem weiteren Grund als verfassungswidrig. Wie bereits dargelegt, ging die erste Instanz bei ihrer Verurteilung wegen versuchten Mords von einer gewollten und gezielten Schussabgabe des Beschwerdeführers in Richtung des fliehenden Beschwerdegegners aus. Davon abweichend erachtet die Vorinstanz (auch) für möglich, dass sich der Schuss - entsprechend der in der Anklageschrift erwähnten Sichtweise des Beschwerdeführers - aus der in das Handgemenge eingebrachten Schusswaffe unbeabsichtigt beim Hantieren mit der Waffe gelöst hat. Selbst wenn die Vorinstanz von dieser Sachverhaltsvariante ohne Verletzung des Anklagegrundsatzes hätte ausgehen dürfen, hätte sie den Beschwerdeführer zwecks Wahrung des rechtlichen Gehörs und aus Gründen der Verfahrensfairness darauf aufmerksam machen müssen, dass sie (auch) bei Zugrundelegung dieses Sachverhalts eine Verurteilung wegen versuchter Tötung bzw. versuchten Mords prüfe und in Betracht ziehe. Aus den gleichen Gründen hätte sie ihm Gelegenheit zur Stellungnahme einräumen müssen. Diesen Verpflichtungen kam die Vorinstanz nicht nach. Entsprechend befassen sich die Ausführungen im Plädoyer der Verteidigung im Hinblick auf den Mordvorwurf denn auch nur mit der dem Beschwerdeführer in der Anklageschrift tatsächlich zur Last gelegten, gezielten und gewollten Schussabgabe auf den fliehenden Beschwerdegegner. Zum Themenkomplex des Auslösens eines unbeabsichtigten Schusses infolge Einbringens der Waffe in das Handgemenge äusserte sich die Verteidigung nicht, weil sie dazu keinen Grund hatte. Mit einer nicht absehbaren rechtlichen Würdigung musste sie bzw. der Beschwerdeführer nicht rechnen. Indem es die Vorinstanz unterliess, diesen auf die ins Auge gefasste juristische Qualifikation des Themenkomplexes des Einbringens einer Waffe in das Gerangel mit unbeabsichtigter Schussauslösung hinzuweisen und ihm Gelegenheit zur Äusserung und Verteidigung zu geben, verletzte sie das Gehörsrecht des Beschwerdeführers sowie den Grundsatz des fairen Verfahrens.
3.4 Die vorinstanzliche Verurteilung wegen versuchten Mords im Sinne von Art. 112 i.V.m. <ref-law> ist in Gutheissung der Beschwerde wegen Verletzung des Anklagegrundsatzes und des rechtlichen Gehörs bzw. des Grundsatzes des fairen Verfahrens aufzuheben. Die Prüfung der weiteren Rügen des Beschwerdeführers (betreffend Mordqualifikation bei versehentlicher Schussauslösung sowie skrupellose Gesinnung) erübrigt sich unter diesen Umständen.
4. Die Beschwerde ist gutzuheissen, das angefochtene Urteil des Appellationsgerichts des Kantons Basel-Stadt aufzuheben und die Sache an die Vorinstanz zur neuen Entscheidung zurückzuweisen.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.
Der Beschwerdegegner Y._ wird als unterliegende Partei kostenpflichtig (<ref-law>). Er stellt ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Dieses ist ebenfalls gutzuheissen, da seine Bedürftigkeit ausgewiesen ist (<ref-law>; vgl. erstinstanzliches Urteil, S. 35 ff.). Sein Standpunkt kann nicht als aussichtslos bezeichnet werden, da er sich der Auffassung der Vorinstanz anschliesst.
Dem Kanton Basel-Stadt sind keine Kosten zu überbinden (<ref-law>).
Dem Rechtsvertreter des Beschwerdeführers ist eine Parteientschädigung zuzusprechen, welche der Beschwerdegegner und der Kanton Basel-Stadt je hälftig zu tragen haben. Bei Uneinbringlichkeit ist der Rechtsvertreter des Beschwerdeführers zufolge Bewilligung des Gesuchs des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung aus der Bundesgerichtskasse zu entschädigen.
Der Rechtsvertreter des Beschwerdegegners Y._ ist zufolge unentgeltlicher Rechtspflege angemessen aus der Bundesgerichtskasse zu entschädigen. Zu berücksichtigen ist dabei, dass sich die Begründung zur Beschwerdeabweisung in einem Verweis auf das vorinstanzliche Urteil erschöpft.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 19. Januar 2011 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. 2.1 Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und Verbeiständung wird gegenstandslos.
2.2 Das Gesuch des Beschwerdegegners Y._ um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen. Für das bundesgerichtliche Verfahren wird ihm Rechtsanwalt Alain Joset, als unentgeltlicher Anwalt beigegeben.
3. Es werden keine Gerichtskosten erhoben.
4. Der Kanton Basel-Stadt und der Beschwerdegegner Y._ haben dem Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren je eine Parteientschädigung von Fr. 1'500.-- zu bezahlen. Bei Uneinbringlichkeit wird der Rechtsvertreter des Beschwerdeführers zufolge Gutheissung des Gesuchs des Beschwerdegegners um unentgeltliche Rechtspflege aus der Bundesgerichtskasse entschädigt.
5. Dem Vertreter des Beschwerdegegners Y._, Rechtsanwalt Alain Joset, wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 1'000.-- ausgerichtet.
6. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 16. September 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill