Sachverhalt:
A. Der italienische Staatsangehörige X._ (geb. 1981) wurde in der Schweiz geboren und ist hier aufgewachsen. Im Jahr 2004 wurde er zu einer Freiheitsstrafe von 3 Jahren verurteilt und in der Folge für unbestimmte Zeit aus der Schweiz ausgewiesen. Nach der Entlassung aus dem Strafvollzug am 18. Mai 2007 verliess X._ die Schweiz.
B. Am 1. März 2011 beantragte X._ beim Bundesamt für Migration (BFM) die Aufhebung der am 26. Juli 2005 auf unbestimmte Zeit angeordneten Ausweisung, die vom Verwaltungsgericht des Kantons Graubünden am 12. Mai 2006 bestätigt worden war. Das BFM leitete das Gesuch zuständigkeitshalber an das Amt für Migration und Zivilrecht des Kantons Graubünden weiter. Dieses nahm die Eingabe als Wiedererwägungsgesuch entgegen und trat mit Verfügung vom 8. Juli 2011 nicht darauf ein. Die dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos.
C. Vor Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Graubünden vom 6. März 2012 aufzuheben und die auf unbestimmte Zeit angeordnete Ausweisung (Einreiseverbot) aufzuheben. Ferner sei ihm für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege zu gewähren.
Das Amt für Migration und Zivilrecht des Kantons Graubünden und das Departement für Justiz, Sicherheit und Gesundheit des Kantons Graubünden verzichteten auf eine Vernehmlassung. Das Verwaltungsgericht des Kantons Graubünden beantragt die Abweisung der Beschwerde. Die Eingabe des BFM erfolgte verspätet und ist daher nicht zu berücksichtigen.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über die Wiedererwägung einer gestützt auf Art. 10 Abs. 1 lit. a und b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) verfügten Ausweisung. Gegenstand des vorliegenden Verfahrens bildet nicht der rechtskräftige Ausweisungsentscheid als solcher, sondern die Frage, ob das Amt für Migration und Zivilrecht des Kantons Graubünden die gerichtlich bestätigte Ausweisung hätte in Wiedererwägung ziehen müssen. Der Beschwerdeführer rügt eine bundesrechtswidrige Anwendung der kantonalen Regeln zur Wiedererwägung, namentlich eine Verletzung seines grundrechtlichen Anspruchs auf Wiedererwägung der Ausweisung bei wesentlicher nachträglicher Änderung der Sach- oder Rechtslage (<ref-law>; vgl. <ref-ruling> E. 6 S. 137 f.; <ref-ruling> E. 3a S. 6; Urteil 2C_114/2011 vom 26. August 2011 E. 2.2; je mit Hinweisen). Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> zur Verfügung (vgl. Urteile 2C_102/2009 vom 11. Juni 2009 E. 1.3; 2C_159/2007 vom 2. August 2007 E. 1.2).
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über die Wiedererwägung einer gestützt auf Art. 10 Abs. 1 lit. a und b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) verfügten Ausweisung. Gegenstand des vorliegenden Verfahrens bildet nicht der rechtskräftige Ausweisungsentscheid als solcher, sondern die Frage, ob das Amt für Migration und Zivilrecht des Kantons Graubünden die gerichtlich bestätigte Ausweisung hätte in Wiedererwägung ziehen müssen. Der Beschwerdeführer rügt eine bundesrechtswidrige Anwendung der kantonalen Regeln zur Wiedererwägung, namentlich eine Verletzung seines grundrechtlichen Anspruchs auf Wiedererwägung der Ausweisung bei wesentlicher nachträglicher Änderung der Sach- oder Rechtslage (<ref-law>; vgl. <ref-ruling> E. 6 S. 137 f.; <ref-ruling> E. 3a S. 6; Urteil 2C_114/2011 vom 26. August 2011 E. 2.2; je mit Hinweisen). Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> zur Verfügung (vgl. Urteile 2C_102/2009 vom 11. Juni 2009 E. 1.3; 2C_159/2007 vom 2. August 2007 E. 1.2).
1.2 1.2.1 Das Bundesgericht prüft von Amtes wegen die formellen Gültigkeitserfordernisse des vorinstanzlichen Verfahrens, insbesondere auch die Frage, ob das kantonale Gericht zu Recht auf die Beschwerde eingetreten ist (Urteil 9C_727/2010 vom 27. Januar 2012 E. 2, nicht publ. in: <ref-ruling>; <ref-ruling> E. 3 S. 25; <ref-ruling> E. 2 S. 9; <ref-ruling> E. 1.2 S. 95). Nach der Rechtsprechung des Bundesgerichts kann indessen aus prozessökonomischen Gründen von der Aufhebung der angefochtenen Verfügung und der Überweisung an die zuständige Behörde abgesehen werden unter der Voraussetzung, dass einerseits die Unzuständigkeit nicht gerügt wird und anderseits aufgrund der gegebenen Aktenlage in der Sache entschieden werden kann (Urteil 9C_891/2010 vom 31. Dezember 2010 E. 2.2 mit Hinweisen).
1.2.2 Die funktionelle oder sachliche Unzuständigkeit einer Behörde kann einen Nichtigkeitsgrund für deren Entscheide darstellen (<ref-ruling> E. 3.3 S. 495 mit Hinweis). Vorausgesetzt ist aber, dass der Mangel besonders schwer und offensichtlich oder zumindest leicht erkennbar ist und die Rechtssicherheit durch die Annahme der Nichtigkeit nicht ernsthaft gefährdet wird (<ref-ruling> E. 3.1 S. 275; <ref-ruling> E. 3.3 S. 495; <ref-ruling> E. 2.1 S. 346).
1.2.3 Die Zuständigkeitsordnung richtet sich nach denjenigen Normen, die bei Eintritt der Rechtshängigkeit des Verfahrens in Kraft sind (vgl. Art. 126 AuG [SR 142.20]; MICHAEL DAUM, in: Auer/Müller/Schindler [Hrsg.], Kommentar zum Bundesgesetz über das Verwaltungsverfahren, 2008, N. 11 zu <ref-law>). Der Beschwerdeführer hat sein Gesuch am 1. März 2011 und damit nach Inkrafttreten des AuG am 1. Januar 2008 eingereicht. Die Zuständigkeit bestimmt sich daher nach diesem Gesetz. Gemäss Art. 67 AuG ist das BFM für den Widerruf (polizeilicher) Einreiseverbote zuständig. Das gilt auch gegenüber einer altrechtlichen Ausweisung, soweit die vollständige oder vorübergehende Aufhebung der mit ihr einhergegangenen (fortdauernden) Fernhaltemassnahme beantragt wird (Urteil 2C_400/2011 vom 2. Dezember 2011 E. 4; vgl. ferner Urteile 2C_36/2009 vom 20. Oktober 2009 E. 3.4; 2C_793/2008 vom 27. März 2009 E. 3.2; 2C_473/2008 vom 17. November 2008 E. 2.3). Die kantonalen Behörden sind dagegen grundsätzlich für die Regelung des Aufenthalts zuständig (vgl. Art. 40 Abs. 1 AuG; <ref-law> [SR 142.203]).
1.2.4 Vorliegend beantragt der Beschwerdeführer, "die am 26. Juli 2005 auf unbestimmte Zeit angeordnete Ausweisung (Einreiseverbot) sei aufzuheben." Dazu führt er aus, es gehe um die Frage, ob das weitere Andauern der Ausweisung, die sich als Einreiseverbot auswirke, rechtmässig sei. Als italienischer Staatsangehöriger habe er gestützt auf Art. 2 Abs. 1 Anhang I des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) das Recht, sich "nach Massgabe dieser Bestimmungen" in der Schweiz aufzuhalten und hier eine Erwerbstätigkeit auszuüben. Dieses Recht dürfe nur unter den Voraussetzungen des Art. 5 Anhang I FZA eingeschränkt werden. Da seine Anwesenheit in der Schweiz keine gegenwärtige und hinreichend schwere Gefahr mehr darstelle, sei das Einreiseverbot aufzuheben.
Der Beschwerdeführer hat sein Gesuch zunächst an das BFM gerichtet, das die Eingabe zuständigkeitshalber an das Amt für Migration und Zivilrecht des Kantons Graubünden weitergeleitet hat. Die kantonalen Behörden haben ihre Zuständigkeit ohne nähere Prüfung bejaht.
1.2.5 Der Beschwerdeführer geht davon aus, dass eine Beschränkung seines gesetzlichen Aufenthaltsrechts gemäss Art. 2 Anhang I FZA nicht (mehr) gerechtfertigt sei und beantragt daher die Aufhebung des Einreiseverbots. Zumindest implizit ersucht der Beschwerdeführer damit auch um eine Regelung seines Aufenthalts, wobei er nicht ausdrücklich zwischen der Aufhebung des Einreiseverbots und der Regelung des Aufenthalts unterscheidet. Diese für die Zuständigkeitsordnung bedeutsame Unterscheidung ist auch vorliegend zu treffen, da das Anmelde- und Bewilligungsverfahren gegenüber Freizügigkeitsberechtigten nicht grundsätzlich entfällt (vgl. dazu <ref-law> i.V.m. Art. 10 ff. AuG und <ref-law> [SR 142.201]; <ref-ruling> E. 2.2 S. 332 f.)
Ungeachtet der mit der Ausweisung angeordneten Fernhaltemassnahme waren die kantonalen Behörden zuständig zu prüfen, ob eine Einschränkung des gesetzlichen Aufenthaltsrechts des Beschwerdeführers (weiterhin) gerechtfertigt und die angeordnete Ausweisung gegebenenfalls in Wiedererwägung zu ziehen bzw. erneut eine Anwesenheitsbewilligung zu erteilen sei (vgl. E. 4.6). Weiter war die sachliche Unzuständigkeit der kantonalen Behörden zur Wiedererwägung des Einreiseverbots infolge der geänderten Zuständigkeitsordnung nicht geradezu offensichtlich oder leicht erkennbar und der angefochtene Entscheid daher nicht nichtig. Unter Berücksichtigung dieser Umstände wie der Tatsache, dass die Unzuständigkeit vom Beschwerdeführer nicht gerügt wurde und die Aktenlage ein Urteil in der Sache erlaubt, rechtfertigt es sich vorliegend nicht, den angefochtenen Entscheid mangels Zuständigkeit aufzuheben.
1.3 Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, und der Beschwerdeführer als direkter Adressat des angefochtenen Entscheids beschwerdebefugt (<ref-law>). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde ist einzutreten.
2. 2.1 Die Vorinstanz hält fest, dass Entfernungs- und Fernhaltemassnahmen auch gegenüber EU/EFTA-Bürgern zulässig seien; dies insbesondere bei schwerwiegenden strafrechtlichen Verbrechen und Vergehen, namentlich bei Gewalt-, Sexual- und Drogendelikten. Die Behandlung des Wiedererwägungsgesuchs richte sich nach den Art. 24 f. des Gesetzes des Kantons Graubünden vom 31. August 2006 über die Verwaltungsrechtspflege (BR 370.100; nachfolgend: VRG). Gegenstand der erneuten Prüfung der Sache könne nur sein, ob sich die relevanten Verhältnisse im Zeitraum seit dem Erlass und dem Vollzug der Ausweisung (Mai 2007) dermassen geändert hätten, dass dem Beschwerdeführer die beantragte Einreise nur mehr erteilt werden müsse. Dagegen gehe es nicht an, die am 12. Mai 2006 gerichtlich bestätigte Ausweisung erneut zu überprüfen. Daher seien die Ausführungen des Beschwerdeführers zu den Umständen vor dem Vollzug der Ausweisung unbeachtlich. Unter Berücksichtigung der Verurteilung zu einer 3-jährigen Zuchthausstrafe wegen Gewalt- und Drogendelikten bestehe nach wie vor ein gewichtiges öffentliches Interesse an der Fernhaltung des Beschwerdeführers, zumal dieser auch keine engen familiären oder verwandtschaftlichen Beziehungen zur Schweiz aufweise. Die frühere Verurteilung könne dem Beschwerdeführer jedoch nicht mehr allzu lange entgegengehalten werden. Dabei sei klar, dass auch eine auf unbestimmte Zeit angeordnete Ausweisung nicht für ewige Zeit gelte, sondern dass das Einreiseverbot bei veränderten Verhältnissen nach einem gewissen Zeitablauf aufgehoben werden könne. Den Behörden stehe aber ein gewisser Ermessensspielraum zu, der vorliegend nicht verletzt worden sei.
2.2 Der Beschwerdeführer rügt, dass der von der Vorinstanz geschützte erstinstanzliche Nichteintretensentscheid seinen verfassungsmässigen Anspruch (<ref-law>) auf Prüfung des Wiedererwägungsgesuchs anhand der heute ersichtlichen Sachumstände verletze. Es gehe nicht darum, die gerichtlich bestätigte Ausweisung und namentlich den darin festgestellten Sachverhalt erneut zu überprüfen, sondern den gegenwärtigen Sachverhalt zu beurteilen. Dabei seien jedoch auch die Umstände zu berücksichtigen, wie sie zum Zeitpunkt der Ausweisung vorgelegen hätten. Ferner verstosse die verweigerte Überprüfung der auf unbestimmte Zeit angeordneten Ausweisung gegen das FZA. Der Beschwerdeführer stelle keine gegenwärtige und hinreichend schwere, das Grundinteresse der Gesellschaft berührende Gefahr für die öffentliche Ordnung dar, sodass die auf unbestimmte Zeit angeordnete Ausweisung vor Art. 5 Anhang I FZA nicht (mehr) standhalte. Zugleich sei Art. 96 AuG verletzt, da die persönlichen Verhältnisse des Beschwerdeführers nicht genügend berücksichtigt worden seien. So könne von irgendwelchen Elementen, die auf eine Rückfallgefahr hinwiesen, keine Rede mehr sein. Das Fehlen einer Zeitbestimmung für das Einreiseverbot sei ohnehin eine unverhältnismässige Massnahme.
3. 3.1 Streitpunkt des vorliegenden Verfahren ist, dass die Vorinstanz auf die (Sach-)Umstände "seit dem Erlass und dem Vollzug der Ausweisung (Mai 2007)" abstellt und nicht eine umfassende Prüfung der Fernhaltemassnahme anhand der gegenwärtigen Sach- und Rechtslage vornimmt. Zu beurteilen ist, ob diese eingeschränkte Prüfung rechtmässig ist oder ob darin eine unzulässige Kognitionsbeschränkung und damit eine formelle Rechtsverweigerung liegt (<ref-law>; Urteil 2C_32/2010, 2C_328/2010 vom 19. Mai 2011 E. 2.3, nicht publ. in: <ref-ruling>; GEROLD STEINMANN, St. Galler Kommentar BV, 2. Aufl. 2008, N. 17 zu <ref-law>, mit Hinweisen).
Die Streitfrage richtet sich vorliegend danach, ob ein ausreichender und zulässiger Grund vorliegt, um auf die gerichtlich bestätigte Ausweisung zurückzukommen und diese anhand der gegenwärtigen Sach- und Rechtslage neu zu prüfen (vgl. <ref-ruling> E. 6.2-6.4 S. 208 ff. mit weiteren Hinweisen; TSCHANNEN/ZIMMERLI/MÜLLER, Allgemeines Verwaltungsrecht, 3. Aufl. 2009, § 31 N. 19 ff.).
3.2 Ob ein Rückkommensgrund vorliegt, bestimmt sich primär nach dem Gesetzesrecht - sei es nach dem Sachgesetz oder dem (kantonalen) Verfahrenserlass. Vorliegend enthalten die Art. 24 f. VRG eine Regelung der Wiedererwägung, behalten dabei aber ausdrücklich spezialgesetzliche Widerrufsregelungen vor (Art. 25 Abs. 3 VRG), was sich mit Blick auf eidgenössische Erlasse bereits aus dem Vorrang des Bundesrechts (<ref-law>) ergibt. Als sachgesetzliche Regelung sind das vom Beschwerdeführer angerufene FZA und die Regelung im AuG näher zu prüfen (vgl. E. 4).
3.3 Subsidiär im Sinne einer verfahrensrechtlichen Minimalgarantie folgt aus <ref-law> ein Anspruch auf Wiedererwägung (vgl. oben E. 1.1; dazu <ref-ruling> E. 2.1 S. 181; Urteil 2C_114/2011 vom 26. August 2011 E. 2.2; je mit Hinweisen). Er greift gegenüber gerichtlich bestätigten Verwaltungsakten namentlich dann, wenn es darum geht, einen zeitlich offenen Dauersachverhalt der im Laufe der Zeit geänderten Sach- und Rechtslage anzupassen (<ref-ruling> E. 4b S. 752 f.; Urteile 2C_274/2009 vom 28. Oktober 2009 E. 1.3; 8C_264/2009 vom 19. Mai 2009 E. 3.2; 1P.563/2002 vom 18. Dezember 2002 E. 2; HÄFELIN/MÜLLER/UHLMANN, Allgemeines Verwaltungsrecht, 6. Aufl. 2010, N. 1833). So trägt dieses Verfahrensgrundrecht bei Fehlen einer gesetzlichen Regelung dazu bei, das Verwaltungsrecht auch in zeitlicher Hinsicht zu verwirklichen und zu vermeiden, dass ein verfügungsweise geregeltes Rechtsverhältnis im Laufe der Zeit nicht mehr durch eine gesetzliche Grundlage gedeckt ist (vgl. <ref-ruling> E. 4b S. 752 f.; TSCHANNEN/ZIMMERLI/MÜLLER, a.a.O., § 31 N. 28).
4. 4.1 Art. 11 Abs. 4 ANAG enthielt eine spezialgesetzliche Grundlage für die Wiedererwägung einer Ausweisung. Die Ausweisung konnte nach dem Gesetzeswortlaut "in Ausnahmefällen vorübergehend eingestellt oder ganz aufgehoben werden". Diese Bestimmung ist per 31. Dezember 2007 ausser Kraft getreten (Ziff. I Anhang 2 AuG) und kann daher vorliegend keine gesetzliche Grundlage für eine Wiedererwägung sein (vgl. Art. 126 AuG). Dies entspricht dem auf dem Legalitätsprinzip fussenden Grundsatz, dass Rechtssätze für die zur Zeit ihrer Geltung sich ereignenden Sachverhalte wirken (ALFRED KÖLZ, Intertemporales Verwaltungsrecht, ZSR 102/1983 II S. 101 ff., S. 160).
4.2 Die Beurteilung, ob ein zulässiger spezialgesetzlicher Rückkommensgrund vorliegt, richtet sich daher nach dem am 1. Januar 2008 in Kraft getretenen AuG. Das Institut der Ausweisung (Art. 10 f. ANAG) ist dem AuG nicht bekannt. Die Ausweisung ordnete in einem einheitlichen Rechtsverhältnis ein Bündel verwaltungsrechtlicher Pflichten, die nach heutigem Recht getrennt zu betrachten sind und Gegenstand eigenständiger Verfügungen bilden können (vgl. Botschaft vom 8. März 2002 zum AuG, BBl 2002 3709, 3809 f. zu Art. 62 E-AuG): der Widerruf der (Niederlassungs-)Bewilligung (Art. 63 AuG), die Wegweisung aus der Schweiz (Art. 64 AuG) und das Einreiseverbot (Art. 67 AuG).
Art. 67 Abs. 5 AuG regelt die Wiedererwägung des Einreiseverbots ausdrücklich und sieht vor, dass die verfügende Behörde "aus humanitären oder anderen wichtigen Gründen von der Verhängung eines Einreiseverbots absehen oder ein Einreiseverbot vollständig oder vorübergehend aufheben" kann. Die sich daraus ergebenden Grundsätze sind auch bei der allfälligen Neuregelung des Aufenthalts zu beachten (vgl. E. 4.6).
4.3 Der Gesetzgeber wählte in Art. 67 Abs. 5 AuG bewusst eine offene Formulierung, um das nationale Recht auf die im übergeordneten Recht geregelten Rückkommensgründe abzustimmen (vgl. Art. 2 AuG; Botschaft vom 18. November 2009 zur Weiterentwicklung des Schengen-Besitzstands, BBl 2009 8881, 8896 f. zu Art. 67 Abs. 5 E-AuG). So enthält namentlich die für die Schweiz im Rahmen des Schengen-Besitzstands relevante sog. "Rückführungsrichtlinie" (Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger, ABl. L 348 vom 24. Dezember 2008 S. 98) in ihrem Art. 11 Abs. 3 eine gesetzliche Ordnung der Rückkommensgründe. Auf den Beschwerdeführer als EU-Bürger ist die "Rückführungsrichtlinie" allerdings nicht anwendbar (Art. 3 Ziff. 1 der Richtlinie 2008/115/EG).
4.3 Der Gesetzgeber wählte in Art. 67 Abs. 5 AuG bewusst eine offene Formulierung, um das nationale Recht auf die im übergeordneten Recht geregelten Rückkommensgründe abzustimmen (vgl. Art. 2 AuG; Botschaft vom 18. November 2009 zur Weiterentwicklung des Schengen-Besitzstands, BBl 2009 8881, 8896 f. zu Art. 67 Abs. 5 E-AuG). So enthält namentlich die für die Schweiz im Rahmen des Schengen-Besitzstands relevante sog. "Rückführungsrichtlinie" (Richtlinie 2008/115/EG des Europäischen Parlaments und des Rates vom 16. Dezember 2008 über gemeinsame Normen und Verfahren in den Mitgliedstaaten zur Rückführung illegal aufhältiger Drittstaatsangehöriger, ABl. L 348 vom 24. Dezember 2008 S. 98) in ihrem Art. 11 Abs. 3 eine gesetzliche Ordnung der Rückkommensgründe. Auf den Beschwerdeführer als EU-Bürger ist die "Rückführungsrichtlinie" allerdings nicht anwendbar (Art. 3 Ziff. 1 der Richtlinie 2008/115/EG).
4.4 4.4.1 Zu prüfen bleibt, ob sich aus dem FZA eine Pflicht zur Wiedererwägung ergibt. Eine Fernhaltemassnahme schränkt das in Art. 3 FZA und Art. 1 Anhang I FZA geregelte Einreiserecht ein. Es handelt sich beim Einreiserecht um das einfachste und grundlegendste der mit der Freizügigkeit verbundenen Rechte, da die Einreise Voraussetzung jeglichen Aufenthalts in der Schweiz ist (<ref-ruling> E. 5 S. 31; Urteil 2C_1045/2011 vom 18. April 2012 E. 2.4). Einschränkungen unterliegen den Voraussetzungen des Art. 5 Anhang I FZA. So rechtfertigt etwa eine frühere strafrechtliche Verurteilung eine Einschränkung der mit der Freizügigkeit gewährten Rechte nur insoweit, als die der Verurteilung zugrunde liegenden Umstände ein persönliches Verhalten erkennen lassen, das eine gegenwärtige Gefährdung der öffentlichen Ordnung darstellt (Art. 5 Abs. 2 Anhang I FZA i.V.m. Art. 3 Abs. 2 der Richtlinie 64/221/EWG des Rates der Europäischen Wirtschaftsgemeinschaft vom 25. Februar 1964 zur Koordinierung der Sondervorschriften für die Einreise und den Aufenthalt von Ausländern, soweit sie aus Gründen der öffentlichen Ordnung, Sicherheit oder Gesundheit gerechtfertigt sind, ABl. Nr. 56, S. 850; Urteil des EuGH vom 27. Oktober 1977 C-30/77 Bouchereau, Slg. 1977 S. 1999 Randnrn. 27 ff.; vgl. auch <ref-ruling> E. 5.3.3 S. 239 f. mit Hinweisen).
Nach der Rechtsprechung des EuGH zur Auslegung der Richtlinie 64/221/EWG stellen Entfernungs- und Fernhaltemassnahmen Ausnahmen vom Grundprinzip der Freizügigkeit dar und können daher nicht auf unbegrenzte Zeit gelten. Diese Rechtsprechung ist von der Schweiz nach Massgabe von Art. 16 Abs. 2 FZA zu beachten. Aus ihr ergibt sich, dass Freizügigkeitsberechtigte nach Ablauf einer "angemessenen Frist" Anspruch auf eine Neubeurteilung der Fernhaltemassnahme nach Massgabe der aktuellen Sachlage haben (Urteil des EuGH vom 17. Juni 1997 C-65/95 und C-111/95 Shingara und Radiom, Slg. 1997 I-3343 Randnrn. 38 ff.; Urteil des EuGH vom 18. Mai 1982 C-115/81 und 116/81 Adoui und Cornuaille, Slg. 1982 S. 1665 Randnr. 12; ALI KIZILDAG, Les mesures restrictives justifiées par l'ordre public en droit communautaire et en droit suisse, RDAF 2004 I S. 469 ff., S. 481 Rz. 34). Dabei ist aufgrund der gegenwärtigen Umstände neu und umfassend zu prüfen, ob (weiterhin) eine gegenwärtige Gefährdung der öffentlichen Ordnung (Art. 5 Abs. 2 Anhang I FZA i.V.m. Art. 3 Abs. 2 der Richtlinie 64/221/EWG) vorliegt.
4.4.2 Wie die Frist konkret zu bemessen ist, lässt sich der EuGH-Rechtsprechung nicht entnehmen. Im Unionsrecht ist die Frist mit Erlass der sog. "Unionsbürgerrichtlinie" konkretisiert worden (Richtlinie 2004/38/EG des Europäischen Parlaments und des Rates vom 29. April 2004 über das Recht der Unionsbürger und ihrer Familienangehörigen, sich im Hoheitsgebiet der Mitgliedstaaten frei zu bewegen und aufzuhalten, ABl. L 158 vom 30. April 2004 S. 77, berichtigt gemäss ABl. L 229 vom 29. Juni 2004 S. 35, geändert gemäss ABl. L 141 vom 27. Mai 2011 S. 1; Vorschlag der Kommission der Europäischen Gemeinschaften vom 23. Mai 2001 für eine Richtlinie des Europäischen Parlaments und des Rates über das Recht der Unionsbürger und ihrer Familienangehörigen, sich im Hoheitsgebiet der Mitgliedstaaten frei zu bewegen und aufzuhalten, COM (2001) 257, Ziff. 1-3 zu Art. 30 E-"Unionsbürgerrichtlinie"). In Art. 32 Abs. 1 der Richtlinie 2004/38/EG ist der Anspruch auf periodische Prüfung ausdrücklich verankert: "Personen, gegen die aus Gründen der öffentlichen Ordnung oder Sicherheit ein Aufenthaltsverbot verhängt worden ist, können nach einem entsprechend den Umständen angemessenen Zeitraum, in jedem Fall aber drei Jahre nach Vollstreckung des nach dem Gemeinschaftsrecht ordnungsgemäss erlassenen endgültigen Aufenthaltsverbots einen Antrag auf Aufhebung des Aufenthaltsverbots unter Hinweis darauf einreichen, dass eine materielle Änderung der Umstände eingetreten ist, die das Aufenthaltsverbot gerechtfertigt haben."
4.4.3 Die "Unionsbürgerrichtlinie" ist für die Schweiz nicht direkt verbindlich (Urteil 2C_213/2012 vom 13. März 2012 E. 2.2.1). Ihre Regeln können daher für die Schweiz nur insofern massgebend sein, als sie dem Sinn und Geist des Freizügigkeitsabkommens entsprechen und diesem zugrunde liegen (<ref-ruling> E. 4.2 S. 74, 120 E. 3.3.1 S. 126 f., 177 E. 3.2.1 S. 184). Es darf sich mit anderen Worten nicht um einen neuen, an die EU-Bürgerschaft anknüpfenden weiterführenden Aspekt der Personenfreizügigkeit innerhalb der Union handeln (<ref-ruling> E. 3.2.1 S. 184). Die in Art. 32 Abs. 1 der Richtlinie 2004/38/EG enthaltene Verpflichtung der Mitgliedstaaten, ein Einreiseverbot ungeachtet seiner Rechtskraft drei Jahre nach Vollstreckung auf Gesuch hin zu überprüfen, berücksichtigt namentlich die hohe Bedeutung, die das Primärrecht dem Unionsbürgerstatus beimisst (vgl. Urteil des EuGH vom 4. Oktober 2012 C-249/11 Byankov, Randnrn. 80 f.). Insofern kann die in der "Unionsbürgerrichtlinie" konkretisierte Frist nicht ohne Weiteres auf das Freizügigkeitsabkommen übertragen werden.
4.4.3 Die "Unionsbürgerrichtlinie" ist für die Schweiz nicht direkt verbindlich (Urteil 2C_213/2012 vom 13. März 2012 E. 2.2.1). Ihre Regeln können daher für die Schweiz nur insofern massgebend sein, als sie dem Sinn und Geist des Freizügigkeitsabkommens entsprechen und diesem zugrunde liegen (<ref-ruling> E. 4.2 S. 74, 120 E. 3.3.1 S. 126 f., 177 E. 3.2.1 S. 184). Es darf sich mit anderen Worten nicht um einen neuen, an die EU-Bürgerschaft anknüpfenden weiterführenden Aspekt der Personenfreizügigkeit innerhalb der Union handeln (<ref-ruling> E. 3.2.1 S. 184). Die in Art. 32 Abs. 1 der Richtlinie 2004/38/EG enthaltene Verpflichtung der Mitgliedstaaten, ein Einreiseverbot ungeachtet seiner Rechtskraft drei Jahre nach Vollstreckung auf Gesuch hin zu überprüfen, berücksichtigt namentlich die hohe Bedeutung, die das Primärrecht dem Unionsbürgerstatus beimisst (vgl. Urteil des EuGH vom 4. Oktober 2012 C-249/11 Byankov, Randnrn. 80 f.). Insofern kann die in der "Unionsbürgerrichtlinie" konkretisierte Frist nicht ohne Weiteres auf das Freizügigkeitsabkommen übertragen werden.
4.5 4.5.1 Das Schweizer Recht enthält zur Fristbestimmung keine ausdrückliche Regelung, wobei aber zu berücksichtigen ist, dass ein Einreiseverbot gemäss Art. 67 Abs. 3 AuG auf höchstens fünf Jahre verfügt wird und diese Maximaldauer nur überschritten werden darf, wenn die betroffene Person eine schwerwiegende Gefahr für die öffentliche Sicherheit und Ordnung darstellt (Art. 67 Abs. 2 und 3 AuG). Diese Regelung ist der "Rückführungsrichtlinie" entnommen (vgl. Art. 11 Abs. 2 der Richtlinie 2008/115/EG; BBl 2009 8881, 8896 zu Art. 67 Abs. 3 E-AuG), wird durch Art. 67 AuG aber grundsätzlich auf sämtliche ausländische Personen - auch Freizügigkeitsberechtigte - anwendbar (vgl. Art. 2 Abs. 2 AuG; <ref-law>; Urteil 2C_318/2012 vom 22. Februar 2013 E. 5.1, zur Publikation vorgesehen). Die Regelhöchstdauer des Einreiseverbots beträgt damit fünf Jahre und kann nur ausnahmsweise für eine längere Dauer verfügt werden. Darüber und über die jederzeit gegebene Möglichkeit, aus "wichtigen Gründen" ein rechtskräftig angeordnetes Einreiseverbot vollständig oder vorübergehend aufzuheben (Art. 67 Abs. 5 AuG), berücksichtigt das Schweizer Recht den aus der einschlägigen EuGH-Rechtsprechung fliessenden Grundsatz, dass Einreiseverbote nicht auf "unbegrenzte Zeit" gelten können und nach Ablauf einer "angemessenen Frist" auf entsprechenden Antrag hin in Wiedererwägung zu ziehen sind.
4.5.2 Diese neue Regelung ist auch für Fernhaltemassnahmen von Bedeutung, die wie die vorliegende noch unter Geltung des ANAG auf unbestimmte Dauer angeordnet worden sind. Folgt aus der einschlägigen EuGH-Rechtsprechung ein Anspruch darauf, dass eine auf unbestimmte Zeit angeordnete Fernhaltemassnahme gegenüber Freizügigkeitsberechtigten nach Ablauf einer angemessenen Frist auf Gesuch hin nach Massgabe der aktuellen Verhältnisse neu beurteilt wird, so ist es zur Bemessung dieser Frist naheliegend, sich an der Regelhöchstdauer des Einreiseverbots zu orientieren und die Frist nicht unter fünf Jahren anzusetzen. Dabei beginnt die Frist mit der Vollstrekkung der Fernhaltemassnahme (Verlassen der Schweiz) und endet mit dem Antrag auf deren Aufhebung.
4.5.3 Es entspricht denn auch der Praxis des Bundesverwaltungsgerichts zur (altrechtlichen) Ausweisung, dass auf unbestimmte Zeit angeordnete Fernhaltemassnahmen nicht "lebenslänglich" oder "ewig" gelten, sondern aufzuheben sind, wenn sie nicht mehr durch ein hinreichendes öffentliches Sicherheitsinteresse gedeckt sind (vgl. BVGE 2008/24 E. 4.3 S. 352 f. und 6.2 S. 354 f.). Angesichts der Vorgaben des Freizügigkeitsrechts und des neu gefassten Art. 67 AuG wird man bei Freizügigkeitsberechtigten entgegen der bisherigen Verwaltungs- und Gerichtspraxis nicht mehr von einer zehnjährigen Frist seit Verbüssung der letzten Freiheitsstrafe ausgehen können (BVGE 2008/24 E. 6.2 S. 354 f; Ziff. 8.9.1.4 der Weisungen des BFM zum Ausländerbereich, Entfernungs- und Fernhaltemassnahmen [Stand: 30. September 2011; abrufbar unter http://www.bfm.admin.ch]). Ob die Frist dabei pauschal auf fünf Jahre anzusetzen ist oder zumindest nach den jeweiligen Umständen auch darüber liegen kann, braucht vorliegend nicht entschieden zu werden, da bei Einreichung des Gesuchs noch keine fünf Jahre verstrichen waren.
4.5.4 Vorbehalten bleiben stets "wichtige Gründe" nach Art. 67 Abs. 5 AuG. Sie können jederzeit vorgebracht werden und dazu führen, dass eine rechtskräftig angeordnete Fernhaltemassnahme vorübergehend oder dauernd aufgehoben wird.
4.6 Die genannten Grundsätze sind von den kantonalen Behörden auch bei einem Gesuch um Regelung des Aufenthalts zu berücksichtigen. Der Anspruch auf periodische Prüfung der Einschränkung der Freizügigkeitsrechte übergreift die nach dem internen Recht vorzunehmende Unterscheidung von Aufhebung des Einreiserverbots und Regelung des Aufenthalts (vgl. E. 1.2.3; Urteil Shingara und Radiom, Randnr. 42). Unabhängig davon, ob der von einer Fernhaltemassnahme betroffene Freizügigkeitsberechtigte beim BFM ein Gesuch um Aufhebung des Einreiseverbots oder bei den kantonalen Behörden ein Gesuch um Neuregelung des Aufenthalts stellt, besteht nach Ablauf einer angemessenen Frist (zu deren Bemessung vgl. E. 4.5) Anspruch darauf, dass die zuständigen Behörden auf das Gesuch eintreten und prüfen, ob (weiterhin) eine gegenwärtige Gefährdung der öffentlichen Ordnung (Art. 5 Abs. 2 Anhang I FZA i.V.m. Art. 3 Abs. 2 der Richtlinie 64/221/EWG) vorliegt.
Ausserhalb dieses periodischen Prüfungsanspruchs sind die kantonalen Behörden namentlich dann gehalten, ungeachtet eines bestehenden Einreiseverbots auf ein Gesuch um Neuregelung des Aufenthalts einzutreten, wenn eine Änderung der Sachlage vorgebracht wird, die derart ins Gewicht fällt, dass ein anderes Ergebnis ernstlich in Betracht fällt (<ref-ruling> E. 2.2.1 S. 181 f.; <ref-ruling> E. 5 S. 504; Urteil 2C_715/2011 vom 2. Mai 2012 E. 4.2). Inhaltlich erfolgt damit eine Abstimmung mit den "wichtigen Gründen" nach Art. 67 Abs. 5 AuG. Über das Zustimmungsverfahren (Art. 40 Abs. 1 AuG und <ref-law> i.V.m. Art. 99 AuG) kann auch die zur Vermeidung von widersprüchlichen Entscheiden gebotene verfahrensmässige Koordination erfolgen. Folge davon ist, dass das Erteilen einer Anwesenheitsbewilligung bei Vorliegen der genannten Voraussetzungen ungeachtet des bestehenden Einreiseverbots zu prüfen und dieses bei Bewilligungserteilung aufzuheben ist (Urteile 2C_400/2011 vom 2. Dezember 2011 E. 4; 2C_793/2008 vom 27. März 2009 E. 3.2; je mit Hinweisen).
5. 5.1 Vorliegend hat der Beschwerdeführer die Schweiz im Mai 2007 verlassen und nach Ablauf von knapp vier Jahren am 1. März 2011 ein Gesuch um Aufhebung der Ausweisung (Einreiseverbot) gestellt. Das Amt für Migration und Zivilrecht des Kantons Graubünden war daher nicht infolge Zeitablaufs gehalten, darauf einzutreten und eine umfassende Prüfung der Sach- und Rechtslage vorzunehmen. Bei dieser Ausgangslage ist nur dann auf ein Wiedererwägungsgesuch einzutreten, wenn der Beschwerdeführer Gründe vorzubringen vermag, die eine materielle Prüfung seines Gesuchs um Aufhebung des Einreiseverbots bzw. um Aufenthaltsregelung rechtfertigen. Dazu zählt namentlich eine Änderung der Sachlage, die derart ins Gewicht fällt, dass ein anderes Ergebnis ernstlich in Betracht fällt (vgl. E. 4.6; Art. 67 Abs. 5 AuG; <ref-ruling> E. 2.2.1 S. 181 f. mit Hinweisen).
5.2 Der Beschwerdeführer führt im Wesentlichen aus, er sei seit seiner bedingten Entlassung aus dem Strafvollzug in seinem Heimatland nicht wieder straffällig geworden und habe beruflich Tritt gefasst. Das Bundesgericht anerkennt, dass der Zeitablauf, verbunden mit Deliktsfreiheit, dazu führen kann, dass das öffentliche Interesse einer Fernhaltemassnahme nachlässt (BGE <ref-ruling> E. 5 S. 504; Urteile 2C_715/2011 vom 2. Mai 2012 E. 4.3; 2C_964/2010 vom 5. Dezember 2011 E. 3.3; 2C_36/2009 vom 20. Oktober 2009 E. 3.2). Dabei besteht jedoch vorliegend kein Grund, das (behauptete) klaglose Verhalten des Beschwerdeführers als hinreichenden Grund für eine Aufhebung des Einreiseverbots oder eine Neuregelung des Aufenthalts zu betrachten. Zum einen wird das korrekte Verhalten vom Beschwerdeführer erwartet. Zum anderen wird der Zeitablauf, verbunden mit Deliktsfreiheit, über den periodischen Anspruch auf Neuüberprüfung aufgefangen, der vorliegend (noch) nicht gegeben ist.
5.3 Weitere Umstände, die allenfalls einen hinreichenden Grund für eine Aufhebung des Einreiseverbots oder eine Neuregelung des Aufenthalts darstellen können, wie etwa enge familiäre Beziehungen zur Schweiz oder anderweitige (grund-)rechtlich geschützte Interessen, bringt der Beschwerdeführer nicht vor. Aus diesem Grund ist die Beschwerde abzuweisen.
6. 6.1 Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>). Es sind keine Parteientschädigungen geschuldet (<ref-law>).
6.2 Der Beschwerdeführer hat in seiner Beschwerde vom 16. Mai 2012 ein Gesuch um unentgeltliche Rechtspflege gestellt und am 25. Juni 2012 ergänzende Unterlagen eingereicht. Die Gewährung der unentgeltlichen Rechtspflege gemäss <ref-law> setzt formell einen Antrag voraus, der ausdrücklich zu stellen, zu begründen und zu belegen ist. Materiell hängt die unentgeltliche Rechtspflege insbesondere vom Nachweis der Bedürftigkeit ab. Es obliegt dem Gesuchsteller, seine aktuellen Einkommens- und Vermögensverhältnisse umfassend aufzuzeigen und soweit wie möglich zu belegen. Kommt er seinen Obliegenheiten nicht nach, ist das Gesuch abzuweisen (Urteile 2C_26/2012 vom 8. Mai 2012 E. 4; 5A_57/2010 vom 2. Juli 2010 E. 7, nicht publ. in: <ref-ruling>, mit Hinweisen).
6.3 Aus den vom Beschwerdeführer mit Eingabe vom 25. Juni 2012 aufgelegten Unterlagen gehen seine aktuellen Einkommens- und Vermögensverhältnisse nicht hervor. Zu seinem aktuellen Vermögensstand äussert sich der Beschwerdeführer nicht ausdrücklich; entsprechende Belege fehlen. Auch die Angaben zu den Einkünften und Ausgaben sind ungenügend: Die Aufstellung zu Einkommen und Ausgaben geht nach den eigenen Ausführungen des Beschwerdeführers nicht von aktuellen, sondern von vergangenen (Zeitraum 2010/2011) und mutmasslichen künftigen Verhältnissen aus. Mit diesen unvollständigen und unklaren Angaben kommt der Beschwerdeführer seinen Obliegenheiten nicht nach, weshalb das Gesuch um unentgeltliche Rechtspflege abzuweisen ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 2. April 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli