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.