Sachverhalt: A. X._ (geb. 1963) ist spanischer Staatsangehöriger. Er zog am 18. Januar 1985 in die Schweiz und erhielt am 30. April 1990 eine Niederlassungsbewilligung (Kanton Freiburg). Am 15. November 1991 meldete er sich bei der Einwohnerkontrolle der Stadt Zug an und zog im September 1992 an die A._-strasse nach E._ (Kanton Zug). In E._ wechselte er in der Folge zweimal seine Wohnadresse; zuletzt zog er an die B._-strasse. Am 26. März 2004 beantragte X._ beim Sozialdienst der Gemeinde E._ Sozialhilfe und reichte dabei einen Untermietvertrag für die B._-strasse vom 30. September 2003 zwischen ihm als Untermieter und C._ als Untervermieter ein. Ab dem 25. August 2004 erhielt er die beantragte Sozialhilfe; die Gemeinde stützte sich für deren Erteilung u.a. auf den Untermietvertrag mit C._. Am 31. Oktober 2005 meldete sich C._ definitiv in E._ ab und gab an, inskünftig in Spanien zu wohnen. Die Kontrollfrist für die Niederlassungsbewilligung von X._ wurde mehrmals verlängert. Am 6. Juli 2007 bestätigte das Bundesgericht die Ablehnung eines Antrags um Zusprechung einer IV-Rente. Am 26. November 2008 ersuchte X._ um eine weitere Verlängerung der Kontrollfrist seiner Niederlassungsbewilligung, dabei gab er als Wohnadresse die B._-strasse in E._ und als Zweck des Aufenthalts "nichterwerbstätig, IV-Abklärung" an. Im Dezember 2009 stellte die Gemeinde E._ fest, dass die Wohnung an der B._-strasse seit dem 17. April 2005 an andere Personen vermietet war. Die Gemeinde orientierte hierüber das Amt für Migration des Kantons Zug. In einem Telefongespräch erteilte sie diesem zudem die Auskunft, dass X._ nie eine neue Adresse gemeldet, jedoch Sozialgelder in der Gemeinde bezogen habe. X._ habe diesen Umstand auf Rückfrage hin damit erklärt, dass C._ ihm fristlos gekündigt habe, worauf er in einer Notwohnung einquartiert worden sei. Das Amt für Migration des Kantons Zug befragte X._ am 14. Januar 2010 zu seiner Wohnsituation. Die Erkenntnisse der Befragung wurden der Gemeinde E._ mitgeteilt. Diese erhob gegen X._ eine Strafanzeige wegen Betrugs (Art. 146 StGB) sowie unrechtmässigen Erwirkens von Leistungen (§ 41bis des Gesetzes über die Sozialhilfe im Kanton Zug vom 16. Dezember 1982). Am 5. Mai 2010 teilte das kantonale Migrationsamt X._ mit, seine Niederlassungsbewilligung sei per 30. Juni 2006 erloschen: Das Migrationsamt sah es als erwiesen an, dass dieser vom 17. April 2005 bis Ende 2009 vorwiegend landesabwesend gewesen und nur noch besuchsweise in die Schweiz eingereist sei. B. Gegen diese Verfügung erhob X._ erfolglos Beschwerde beim Regierungsrat des Kantons Zug. Eine gegen diesen Entscheid gerichtete Beschwerde an das Verwaltungsgericht des Kantons Zug wies dieses mit Urteil vom 27. März 2012 ab. C. Mit Eingabe vom 15. Mai 2012 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht und beantragt, der Entscheid des Verwaltungsgerichts des Kantons Zug sei aufzuheben; ihm sei die Niederlassungsbewilligung zu belassen. Eventuell sei die Sache bezüglich der Erteilung einer Aufenthaltsbewilligung an die Vor- oder erste Instanz zurückzuweisen. X._ ersucht um unentgeltliche Prozessführung und Verbeiständung. Das Verwaltungsgericht des Kantons Zug beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Es weist darauf hin, dass die Frage des Erlöschens der Niederlassungsbewilligung infolge Landesabwesenheit und ein allfälliger Sozialhilfemissbrauch zu trennen seien, weshalb es den Sozialhilfebezug konsequent aus seinem Urteil ausgeklammert habe. Der Eventualantrag (Prüfung eines allfälligen Aufenthaltsanspruchs) sei ohne Begründung erhoben worden, weshalb ihn das Verwaltungsgericht nicht habe behandeln können. Das Amt für Migration des Kantons Zug verzichtet auf eine umfassende Vernehmlassung, weist jedoch darauf hin, dass die Aktennotizen auf Post-it-Klebern zu Telefongesprächen in die Protokolle vom 14. Januar 2010 (Befragung zur Wohnsituation) Eingang gefunden hätten, sodass der Beschwerdeführer hiervon Kenntnis gehabt habe. Im Übrigen beantragt es die Abweisung der Beschwerde. Der Regierungsrat des Kantons Zug (Sicherheitsdirektion) weist darauf hin, bei der Meldung der Gemeinde an das kantonale Ausländeramt, wonach der Beschwerdeführer offenbar keinen Wohnsitz (mehr) an der von ihm gemeldeten Adresse habe, handle es sich nicht um eine Meldung hinsichtlich eines allfälligen missbräuchlichen Bezugs von Sozialhilfe; die Verfahren seien zu trennen. Der Gemeinde stehe es zu, das kantonale Ausländeramt über An- und Abmeldungen ausländischer Personen zu informieren. Es seien deshalb keine Datenschutzbestimmungen und Geheimhaltungsverpflichtungen verletzt worden. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen. Mit Verfügung vom 23. Mai 2012 hat der Präsident der Beschwerde aufschiebende Wirkung zuerkannt.