Erwägungen:
1. 1.1 Der aus Serbien (Kosovo) stammende X._ (geb. 1982) heiratete am 9. August 2002 die in der Schweiz niedergelassene Mazedonierin Y._ und reiste am 3. Oktober 2002 in die Schweiz ein. Am 9. Juni 2005 wurde der gemeinsame Sohn geboren. Ab dem Zeitpunkt der Einreise - ausser vom 1. Januar 2007 bis zum 31. August 2007 - musste X._ von der Sozialhilfe unterstützt werden. Zusätzlich lagen Verlustscheine in der Höhe von über Fr. 50'000.-- vor. Am 7. März 2008 wurde X._ wegen mehrfachen Betrugs, versuchten Betrugs, Anstiftung zur Sachbeschädigung und Irreführung der Rechtspflege zu einer bedingten Geldstrafe von 180 Tagessätzen verurteilt. Mit Verfügung vom 14. Dezember 2009 verweigerte das zuständige Migrationsamt die Verlängerung der Aufenthaltsbewilligung und wies X._ aus der Schweiz weg. Das Bundesgericht bestätigte diesen Entscheid am 3. Oktober 2011 (2C_345/2011). Es bejahte die Widerrufsgründe der Sozialhilfeabhängigkeit (Art. 62 lit. e AuG [SR 142.20]) sowie des Verstosses gegen die öffentliche Sicherheit und Ordnung (Art. 62 lit. c AuG) wegen mutwilliger Schuldenmacherei und deliktischer Tätigkeiten.
Am 4. Januar 2010 nahm X._ eine vollzeitliche Erwerbstätigkeit auf. Die Ehefrau arbeitet nach Absolvierung ihrer Ausbildung zur Pflegeassistentin seit dem 15. Oktober 2011 ebenfalls in einem Vollzeitpensum. Die Eheleute sind in den letzten zwei Jahren ihren finanziellen Verpflichtungen grösstenteils nachgekommen und haben begonnen, Schulden abzubauen. Der Betreibungsregisterauszug von X._ vom 14. Mai 2012 weist 27 offene Verlustscheine in der Höhe von Fr. 49'492.90 aus. Am 2. März 2011 wurde X._ erneut wegen mehrfachen Betrugs zu einer bedingten Geldstrafe von 180 Tagessätzen und einer Busse von Fr. 800.-- verurteilt.
1.2 Am 29. November 2011 reichte X._ ein Gesuch um Wiedererwägung ein, auf welches das Migrationsamt des Kantons Basel-Stadt am 8. Dezember 2011 nicht eintrat. Die dagegen erhobenen kantonalen Rechtsmittel blieben erfolglos.
1.3 Vor Bundesgericht beantragt X._, das Urteil des Appellationsgerichts des Kantons Basel-Stadt (als Verwaltungsgericht) vom 11. Juni 2012 aufzuheben und die Sache zu materiellem Entscheid an das Migrationsamt des Kantons Basel-Stadt zurückzuweisen.
2. 2.1 Streitgegenstand bildet die Frage, ob die kantonalen Behörden aufgrund neuer erheblicher Tatsachen auf das vom Beschwerdeführer gestellte Wiedererwägungsgesuch hätten eintreten müssen (zum bundesrechtlichen Anspruch auf Wiedererwägung: Art. 29 BV; BGE 136 II 177 E. 2.1 S. 181; 127 I 133 E. 6 S. 137 f. mit Hinweisen). Der kassatorische Antrag des Beschwerdeführers ist vorliegend zulässig, da das Bundesgericht nicht in der Sache selbst entscheiden kann (Art. 42 Abs. 1 i.V.m. Art. 107 BGG; vgl. Urteile 4A_402/2011 vom 19. Dezember 2011 E. 1.1; 2C_682/2009 vom 8. April 2010 E. 1.4).
Als Ehegatte einer Person mit Niederbelassungsbewilligung verfügt der Beschwerdeführer grundsätzlich über einen Anspruch auf eine Aufenthaltsbewilligung in der Schweiz (Art. 43 Abs. 1 AuG), sodass die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen den kantonal letztinstanzlichen Entscheid zulässig ist (Art. 82 lit. a, Art. 83 lit. c Ziff. 2 [e contrario], Art. 86 Abs. 1 lit. d und Art. 90 BGG). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde ist daher einzutreten.
2.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz auf genügend begründete Rüge hin (Art. 106 Abs. 2 BGG) oder von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 BGG; Urteil 2C_1039/2012 vom 16. Februar 2013 E. 1.2).
Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (BGE 138 I 274 E. 1.6 S. 280 f. mit Hinweis). Die Verletzung von Grundrechten untersucht es in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
3. Wenn die Vorinstanz davon ausgegangen ist, es seien keine wesentlichen Änderungen auszumachen, die eine Neubeurteilung rechtfertigen, ist dies nicht bundes(verfassungs-)rechtswidrig:
3.1 Ob ein Wiedererwägungsgesuch in Fällen wie dem vorliegenden materiell zu behandeln ist, hängt davon ab, ob sich der Sachverhalt oder die Rechtslage in einer Art geändert haben, dass ein anderes Ergebnis ernstlich in Betracht kommt (BGE 136 II 177 E. 2.2.1 S. 181 f.; Urteile 2C_574/2012 vom 19. Februar 2013 E. 2.2; 2C_1039/2012 vom 16. Februar 2013 E. 3.1; 2C_715/2011 vom 2. Mai 2012 E. 2.2; 2C_274/2009 vom 28. Oktober 2009 E. 2.2). Massgebend ist dabei eine Gesamtbetrachtung: Auch wenn sich einzelne Umstände ändern, die bei der Abwägung im früheren Entscheid mitberücksichtigt worden sind, besteht nur dann Anspruch auf eine erneute materielle Prüfung, wenn ein anderes Ergebnis realistischerweise möglich ist (vgl. WIEDERKEHR/RICHLI, Praxis des allgemeinen Verwaltungsrechts, 2012, N. 2662). Soweit sich weder die Sach- noch die Rechtslage in rechtserheblicher Weise geändert haben, steht die Rechtskraft des früheren Entscheids der Wiedererwägung entgegen. Diese darf namentlich nicht bloss dazu dienen, rechtskräftige Entscheide immer wieder infrage zu stellen oder die Fristen für die Ergreifung von Rechtsmitteln zu umgehen (BGE 136 II 177 E. 2.1 S. 181; Urteile 2C_1039/2012 vom 16. Februar 2013 E. 3.1; 2C_598/2011 vom 26. Juli 2011 E. 2.2.1).
3.2 Wenige Wochen nach dem bundesgerichtlichen Entscheid vom 3. Oktober 2011 stellte der Beschwerdeführer am 29. November 2011 ein Wiedererwägungsgesuch. Er brachte mehrere Elemente vor, die nach seiner Auffassung für eine erhebliche Veränderung der Verhältnisse sprechen: sein fortdauerndes Arbeitsverhältnis, die Erwerbstätigkeit der Ehefrau, der Zusatzverdienst als Hauswarte, das daraus resultierende Familieneinkommen von monatlich über Fr. 8'000.-- (netto) sowie ein massiver Schuldenabbau bzw. eine Schuldentilgung in absehbarer Zeit.
3.3 Das Bundesgericht hat seinem Urteil vom 3. Oktober 2011 (2C_345/2011) den Sachverhalt zugrunde gelegt, wie ihn das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 3. März 2011 festgestellt hatte; die eingereichten Noven blieben unberücksichtigt (vgl. Art. 97, 99 und 105 BGG). Damit waren Umstände, die nach dem 3. März 2011 eingetreten sind, bislang nicht Gegenstand einer (bundes-)gerichtlichen Beurteilung und können vom Beschwerdeführer grundsätzlich im Rahmen eines Wiedererwägungsgesuchs vorgebracht werden. Sie vermögen jedoch eine Neubeurteilung nicht zu rechtfertigen:
3.3.1 Ausschlaggebend für die Bejahung des Widerrufsgrundes nach Art. 62 lit. e AuG (Sozialhilfeabhängigkeit) war, dass der Beschwerdeführer in den Jahren, in denen er über ein geregeltes Anwesenheitsrecht verfügte, abgesehen von einer kurzen Zeitspanne, durchwegs von der Sozialhilfe unterstützt werden musste und massive Schulden anhäufte. Dieses langjährige Verhalten des Beschwerdeführers trug massgeblich dazu bei, dass auch künftig eine Unterstützungsbedürftigkeit befürchtet werden musste. Ferner wies das Bundesgericht darauf hin, dass sich der Beschwerdeführer wie seine Ehefrau erst unter dem Druck der drohenden Wegweisung um die Aufnahme einer Erwerbstätigkeit bzw. einer Ausbildung bemühten.
3.3.2 Die Sachumstände, die der bundesgerichtlichen Würdigung vom 3. Oktober 2011 zugrunde lagen, haben sich in der Zwischenzeit nicht erheblich verändert: Zwar hat sich die finanzielle Situation des Beschwerdeführers und seiner Familie unstrittig entspannt, auch wenn weiterhin offene Verlustscheine in beträchtlicher Höhe bestehen. Doch zeichnete sich dies bereits am 3. März 2011 ab und wurde im Urteil vom 3. Oktober 2011 ausdrücklich mitberücksichtigt (vollzeitliche Erwerbstätigkeit des Beschwerdeführers; berufliche Ausbildung der Ehefrau). Die relative kurze Zeitspanne von knapp neun Monaten zwischen dem 3. März 2011 und dem Stellen des Wiedererwägungsgesuchs am 29. November 2011 ist vorliegend nicht geeignet, eine erhebliche Sachverhaltsänderung herbeizuführen. Vielmehr legt es das Vorgehen des Beschwerdeführers nahe, dass er neue Sachzwänge zu schaffen versucht, um in einem Wiedererwägungsverfahren den rechtskräftigen Entscheid (immer wieder) infrage zu stellen und sich dann auf den mit diesem Verfahren verbundenen Zeitablauf berufen zu können. Solches Verhalten ist nicht schutzwürdig, würde doch sonst schlechtergestellt, wer sich an die ihm auferlegte (rechtskräftige) Ausreisepflicht hält (vgl. Urteil 2C_598/2011 vom 26. Juli 2011 E. 2.2.1).
3.3.3 Bei der erforderlichen Gesamtbetrachtung ist die erneute Verurteilung des Beschwerdeführers zu einer Geldstrafe von 180 Tagen wegen mehrfachen Betrugs zu berücksichtigen. Diese Verurteilung vom 2. März 2011 war gemäss unbestrittener Feststellung der Vorinstanz am 3. März 2011 nicht aktenkundig. Die erneute, nicht unerhebliche Delinquenz bekräftigt das Vorliegen des Widerrufsgrundes nach Art. 62 lit. c AuG, der bereits im Urteil vom 3. Oktober 2011 bejaht worden ist.
4. Aus den vorstehenden Erwägungen ergibt sich, dass die Beschwerde offensichtlich unbegründet ist. Sie ist daher im Verfahren nach Art. 109 Abs. 2 lit. a BGG abzuweisen. Bei diesem Verfahrensausgang hat der Beschwerdeführer die Kosten des Verfahrens zu tragen (Art. 65 f. BGG). Es sind keine Parteientschädigungen geschuldet (Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 19. März 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Egli