Sachverhalt: A. A.a. Der marokkanische Staatsangehörige X._ (geb. 1982) reiste am 30. April 2006 unter falschen Personalien in die Schweiz ein und stellte hier erfolglos ein Asylgesuch. Am 26. Oktober 2006 wurde er nach Deutschland überstellt, wo er bereits früher erfolglos einen Asylantrag gestellt hatte. A.b. Am 19. Dezember 2007 reichte X._ (unter richtigem Namen) auf der schweizerischen Botschaft in Marokko ein Gesuch um Bewilligung der Einreise zur Vorbereitung der Heirat mit der Schweizerin Y._ (geb. 1980) ein. Nach Gutheissung des Gesuchs reiste X._ am 29. März 2008 in die Schweiz ein, wo er am 19. Mai 2008 heiratete und in der Folge eine Aufenthaltsbewilligung erhielt. Die Eheleute haben einen gemeinsamen Sohn (geb. 2010). Am 19. Mai 2011 informierte Y._ das Amt für Migration des Kantons Basel-Landschaft über die Trennung der Eheleute und das einstweilige weitere Zusammenwohnen, bis X._ eine neue Wohnung gefunden habe. Die Unterzeichnung der Scheidungskonvention erfolgte am 26. Mai 2011, die Auflösung der Wohngemeinschaft am 1. Juli 2011 und die Scheidung am 16. August 2011. Die elterliche Sorge über den gemeinsamen Sohn wurde Y._ zugeteilt. X._ erhielt ein wöchentliches Besuchsrecht von zwei Stunden in Begleitung von Y._. Auf ein Ferienrecht wurde altershalber verzichtet und X._ verpflichtet, ab 1. März 2012 einen monatlichen Kinderunterhaltsbeitrag in der Höhe von Fr. 400.-- (zzgl. Kinderzulagen) zu bezahlen. A.c. Am 7. August 2011 erfuhr das Amt für Migration des Kantons Basel-Landschaft von Y._, dass X._ mehrere Jahre unter falschem Namen in Deutschland gelebt habe und dort mehrfach verurteilt worden sei. Gegenüber den Schweizer Behörden hatte X._ im Rahmen des Familiennachzugs das Vorliegen von Vorstrafen verneint (Formular "Fremdenpolizeiliche Anmeldung" vom 20. Mai 2008). Eine Auskunft der deutschen Behörden vom 23. August 2011 ergab, dass gegen X._ in Deutschland zwischen 2004 und 2006 insgesamt vier Verurteilungen ergangen waren: Am 21. Juli 2004 war er wegen Diebstahls in sechs Fällen zu einer Jugendstrafe (Freiheitsentzug) von 6 Monaten verurteilt worden, am 3. November 2004 wegen Diebstahls zu 10 Monaten, am 13. April 2005 wegen Diebstahls zu 13 Monaten und am 6. Dezember 2006 wegen Diebstahls in zwei Fällen und Beleidigung zu 18 Monaten. Die ausgesprochenen Strafen waren jeweils unter Einbezug der vorangegangenen Verurteilungen (sog. Einheitsstrafe nach § 31 des deutschen Jugendgerichtsgesetzes) erfolgt. B. Am 25. Oktober 2011 verweigerte das Amt für Migration des Kantons Basel-Landschaft die Verlängerung der Aufenthaltsbewilligung von X._ und wies ihn aus der Schweiz weg. Die dagegen erhobene Beschwerde wies der Regierungsrat des Kantons Basel-Landschaft am 8. Mai 2012 ab. Die anschliessende Beschwerde beim Kantonsgericht Basel-Landschaft blieb erfolglos (Urteil vom 12. Dezember 2012). C. Vor Bundesgericht beantragt X._, das Urteil des Kantonsgerichts Basel-Landschaft vom 12. Dezember 2012 aufzuheben und ihm weiterhin den Aufenthalt im Kanton Basel-Landschaft zu bewilligen, eventualiter die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Zudem sei ihm im bundesgerichtlichen Verfahren die unentgeltliche Rechtspflege zu gewähren. Das Kantonsgericht Basel-Landschaft verzichtet auf eine Vernehmlassung. Der Regierungsrat des Kantons Basel-Landschaft und das Bundesamt für Migration (BFM) beantragen die Abweisung der Beschwerde. D. Am 8. Februar 2013 hat der Abteilungspräsident der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.