Sachverhalt:
A. Der mazedonische Staatsangehörige X._ (geb. 1985) heiratete am 13. April 2005 in seiner Heimat die in der Schweiz geborene und niedergelassene serbische Staatsangehörige Y._ (geb. 1988). Am 24. Oktober 2005 reiste er in die Schweiz ein und erhielt eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Im Mai 2007 kam die gemeinsame Tochter Z._ zur Welt. Mit Eheschutzverfügung vom 23. Juni 2008 stellte das Richteramt A._ fest, dass die Ehegatten seit dem 23. April 2008 getrennt lebten. Per 1. Juli 2009 nahmen die Eheleute die Haushaltsgemeinschaft wieder auf, worauf die Migrationsbehörde des Kantons Solothurn mit Verfügung vom 22. Juli 2009 die Aufenthaltsbewilligung von X._ verlängerte. Im Dezember 2009 kam es zur erneuten Trennung der Eheleute. Mit Urteil vom 19. Mai 2011 des Richteramtes A._ wurde die Ehe auf Antrag beider Parteien geschieden und die elterliche Sorge über die Tochter Z._ der Mutter zugeteilt.
B. Am 30. Mai 2011 verfügte die Migrationsbehörde, dass die Aufenthaltsbewilligung von X._ nicht verlängert werde und dieser die Schweiz bis zum 31. August 2011 zu verlassen habe. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 4. November 2011 ab und forderte X._ auf, die Schweiz bis zum 31. Januar 2012 zu verlassen.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 8. Dezember 2011 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 4. November 2011 sei aufzuheben und seine Aufenthaltsbewilligung sei zu verlängern. Gerügt wird die Verletzung von Bundesrecht sowie von <ref-law> bzw. Art. 8 EMRK.
D. Das Verwaltungsgericht und die Migrationsbehörde des Kantons Solothurn beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde.
Mit Verfügung vom 13. Dezember 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Nach <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide ausgeschlossen, auf deren Erteilung weder das Bundes- noch das Völkerrecht einen Anspruch einräumt. Der Beschwerdeführer macht geltend, trotz des Scheiterns der Ehe mit seiner in der Schweiz niedergelassenen Gattin gestützt auf Art. 50 AuG und Art. 8 EMRK (bzw. <ref-law>) über einen Bewilligungsanspruch zu verfügen. Seine Vorbringen sind nicht offensichtlich untauglich, den behaupteten Bewilligungsanspruch zu begründen. Ob die Voraussetzungen für die Bewilligungserteilung gegeben sind, bildet Gegenstand der materiellen Beurteilung (Urteil 2C_830/2010 vom 10. Juni 2011 E. 1.1 mit Hinweis). Für das Eintreten genügt, dass im Rahmen von Art. 42 ff. AuG potenziell ein solcher Anspruch besteht (vgl. <ref-ruling> E. 1.1 S. 179).
Auf das im Übrigen form- und fristgerecht eingereichte Rechtsmittel (Art. 42 und Art. 100 Abs. 1 BGG) ist daher grundsätzlich einzutreten (unter Vorbehalt von E. 1.2 und E. 1.3 hiernach).
1.2 Das Bundesgericht legt seinem Urteil die Sachverhaltsfeststellungen der Vorinstanz zugrunde (<ref-law>). Mit einer Beschwerde in öffentlich-rechtlichen Angelegenheiten können diese nur dann gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich sind (<ref-ruling> E. 1.2.2 S. 252; <ref-ruling> E. 7.1 S. 398) oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen. Zudem ist vom Beschwerdeführer aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
1.3 Die Beschwerdeschrift hat gemäss <ref-law> die Begehren und deren Begründung zu enthalten; im Rahmen der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheides auseinandersetzt (<ref-ruling> E. 2.1 S. 245 f.). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insoweit, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>).
2. 2.1 Ausländische Ehegatten von niedergelassenen Ausländern haben grundsätzlich einen Anspruch auf Erteilung und Verlängerung ihrer Aufenthaltsbewilligung, wenn sie mit ihrem Partner zusammenwohnen (Art. 43 Abs. 1 AuG). Der Bewilligungsanspruch besteht trotz Auflösens bzw. definitiven Scheiterns der Ehegemeinschaft fort, wenn diese mindestens drei Jahre gedauert und die betroffene ausländische Person sich hier zudem erfolgreich integriert hat (Art. 50 Abs. 1 lit. a AuG) oder wichtige persönliche Gründe einen weiteren Aufenthalt in der Schweiz erforderlich machen (Art. 50 Abs. 1 lit. b AuG).
2.2 Von einer (relevanten) Ehegemeinschaft ist auszugehen, solange die eheliche Beziehung tatsächlich gelebt wird und ein gegenseitiger Ehewille besteht. Mit Blick auf Art. 49 AuG, der den Ehegatten bei weiterdauernder Familiengemeinschaft gestattet, aus "wichtigen Gründen" getrennt zu leben, was auch bei vorübergehenden Schwierigkeiten in der Ehe kurzfristig der Fall sein kann, ist jeweils aufgrund sämtlicher Umstände im Einzelfall zu bestimmen, ab welchem Zeitpunkt die eheliche Gemeinschaft als definitiv aufgelöst zu gelten hat. Dabei ist im Wesentlichen auf die Dauer der nach aussen wahrnehmbaren ehelichen Wohngemeinschaft abzustellen (Urteil 2C_544/2010 vom 23. Dezember 2010 E. 2.2). Für die Berechnung der Frist von drei Jahren ist ausschliesslich die in der Schweiz gemeinsam verbrachte Zeit massgebend (<ref-ruling> E. 3.3 S. 117 ff.).
Zwar hält sich der Beschwerdeführer seit 2005 in der Schweiz auf und hat hier mit seiner damaligen Ehegattin unbestrittenermassen über drei Jahre zusammengelebt (vgl. angefochtener Entscheid E. 2b), doch kann nicht gesagt werden, dass er sich erfolgreich in die hiesigen Verhältnisse integriert hätte (vgl. auch Art. 77 Abs. 4 der Verordnung vom 24. Oktober 2007 über die Zulassung, Aufenthalt und Erwerbstätigkeit, VZAE; SR 142.201): Dagegen sprechen zunächst die Ausstände der Unterhaltsbeiträge an seine Tochter bzw. die Ehefrau (rund Fr. 41'000.--), die Anhäufung von Schulden (fünf Verlustscheine über Fr. 14'667.45 bzw. neun Betreibungen in der Höhe von Fr. 4'077.30) sowie die fehlende Teilnahme am Wirtschaftsleben (vgl. angefochtener Entscheid E. 2c). Zwar ist positiv zu werten, dass der Beschwerdeführer gute Deutschkenntnisse ausweisen kann, gegen ihn keine rechtskräftigen Verurteilungen (aber immerhin mehrfache Strafanzeigen) vorliegen und er bis November 2010 einer Erwerbstätigkeit nachging, doch ergibt sich daraus insgesamt noch keine erfolgreiche Integration. Der Beschwerdeführer behauptet zwar eine solche, belegt diese entgegen seinen verfahrensrechtlichen Mitwirkungspflichten indessen nicht weiter (vgl. Art. 90 AuG). Er führt einzig dazu aus, ihn treffe weder an der Existenz der Verlustscheine noch an den ausstehenden Unterhaltsbeiträgen eine Schuld. Diese nicht näher belegten pauschalen Behauptungen vermögen keine erfolgreiche Integration des Beschwerdeführers zu begründen.
2.3 Der Beschwerdeführer beruft sich sodann auf einen wichtigen persönlichen Grund im Sinne von Art. 50 Abs. 1 lit. b AuG. Ein persönlicher nachehelicher Härtefall gemäss dieser Bestimmung setzt aufgrund der gesamten Umstände des Einzelfalls eine erhebliche Intensität der Konsequenzen für das Privat- und Familienleben voraus. Dem Schutz des Familienlebens nach Art. 8 EMRK und <ref-law> ist im Rahmen von Art. 50 AuG Rechnung zu tragen. Insoweit ist namentlich zu berücksichtigen, ob der Ausländer Kinder in der Schweiz hat (vgl. Urteile 2C_195/2010 vom 23. Juni 2010 E. 6; 2C_830/2010 vom 10. Juni 2011 E. 3; je mit Hinweisen). Nach der ständigen Praxis zu den erwähnten Verfassungs- und Konventionsbestimmungen ist dem ausländischen Elternteil, der nicht mit seinen Kindern zusammenlebt, der Aufenthalt dann zu gewähren, wenn zwischen ihm und den Kindern in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung besteht, die wegen der Distanz zu seinem Herkunftsland praktisch nicht aufrechterhalten werden könnte, und wenn zusätzlich das bisherige Verhalten des Ausländers zu keinerlei Klagen Anlass gegeben hat (zu Art. 8 EMRK: <ref-ruling> E. 3c S. 5, 22 E. 4a und b S. 25 f.; zu Art. 50 AuG: erwähntes Urteil 2C_195/2010 E. 6.6).
2.3.1 Die Vorinstanz hat hierzu festgestellt, eine besonders enge affektive Beziehung zu seiner Tochter sei nicht dargetan. Auch in wirtschaftlicher Hinsicht bestehe keine besonders enge Beziehung (vgl. angefochtener Entscheid E. 2d). Diese Ausführungen sind nicht zu beanstanden: Der Umstand, dass nur an zwei Tagen pro Monat begleitete Besuche stattfinden, ist keineswegs geeignet darzutun, dass eine (besonders) enge Beziehung zu seiner Tochter besteht. Was das Erfordernis der besonderen Intensität der affektiven Beziehung betrifft, ist dieses nämlich bloss dann als erfüllt zu erachten, wenn ein grosszügig ausgestaltetes Besuchsrecht eingeräumt ist und dieses kontinuierlich, spontan und reibungslos ausgeübt wird (vgl. Urteil 2C_799/2010 vom 20. Februar 2011 E. 3.3.1 mit Hinweisen). Wohl auch bedingt durch die ablehnende Haltung der Mutter ist es dem Beschwerdeführer bisher nicht gelungen, wesentliche Betreuungsfunktionen zu übernehmen und ein kontinuierlich gepflegtes Verhältnis zu seiner Tochter aufzubauen. Der Beschwerdeführer gibt selber zu, dass es sich hier nicht um ein grosszügiges Besuchsrecht handle; er führt diesen Umstand darauf zurück, dass die Mutter das Besuchsrecht des Beschwerdeführers "systematisch hintertrieben" habe. Dagegen ist einzuwenden, dass ein Erziehungsbeistand das Besuchsrecht zu organisieren hat und die Vorinstanz dazu festgestellt hat, dass zwischen Oktober 2010 und Mai 2011 an neun Tagen und ab Mai 2011 monatlich zwei Mal Besuche stattgefunden haben. Im Lichte der bundesgerichtlichen Rechtsprechung geht das Besuchsrecht damit nicht über das übliche Mass hinaus (vgl. etwa Urteile 2C_335/2009 vom 12. Februar 2010 E. 2.2.3; 2C_194/2009 vom 24. Juni 2009 E. 3.1; 2C_171/2009 vom 3. August 2009 E. 2.3; 2C_870/2008 vom 26. Mai 2009 E. 2.2.1). Schliesslich bringt der Beschwerdeführer auch nichts vor, was auf eine mehr als normale Vater-Tochter-Beziehung hindeuten würde.
2.3.2 Die Vorinstanz hat sodann verbindlich festgestellt, dass der Beschwerdeführer seinen Unterhaltsverpflichtungen kaum je nachgekommen ist (vgl. angefochtener Entscheid E. 2d). Auch der Beschwerdeführer bestreitet nicht, dass er seiner Unterhaltspflicht "nicht lückenlos" nachgekommen ist. Damit ist der Schluss der Vorinstanz, es bestehe auch in wirtschaftlicher Hinsicht keine besonders enge Beziehung zu seiner Tochter, nicht zu beanstanden. Namentlich kann der Beschwerdeführer mit dem Hinweis, die Unterhaltsbeiträge seien bevorschusst worden, nichts zu seinen Gunsten ableiten.
2.3.3 Der Hinweis des Beschwerdeführers auf das Urteil des Europäischen Gerichtshofs für Menschenrechte (EGMR) vom 11. Juli 2000 i.S. Ciliz gegen die Niederlande (Recueil CourEDH 2000-VIII S. 291) ist ebenfalls unbehelflich. In diesem Fall wurde ein Türke während des Verfahrens über die Besuchsregelung für seinen Sohn ausgewiesen. Den niederländischen Behörden war insbesondere vorgeworfen worden, dass sie dem Ausländer nach erfolgter Ausschaffung durch Verweigerung eines Visums nicht mehr ermöglicht hatten, persönlich am Verfahren zur Regelung des Besuchsrechts und an vom Familiengericht zu Evaluationszwecken angeordneten Treffen mit dem Kind ("rencontres-tests") teilzunehmen. Darum geht es im vorliegenden Fall aber nicht. Davon abgesehen hat der EGMR im erwähnten Urteil nicht grundsätzlich beanstandet, dass ein Ausländer das Verfahren zur Regelung des Besuchsrechts bezüglich eines Kindes von der Heimat aus betreiben muss, solange ihm die dabei nötigen Einreisen nicht verwehrt werden (vgl. Urteil 2C_7/2008 vom 29. Januar 2008 E. 4.1).
2.3.4 Der Schluss der Vorinstanz, zwischen dem Beschwerdeführer und seiner Tochter bestehe weder in wirtschaftlicher noch in affektiver Hinsicht eine besonders enge Beziehung, ist somit nicht zu beanstanden. Bei dieser Sachlage kommt dem Umstand, dass der Beschwerdeführer sein Besuchsrecht von Mazedonien aus nur beschränkt und mit Schwierigkeiten verbunden wird ausüben können, keine entscheidende Bedeutung zu. Dies umso weniger, als der Beschwerdeführer sich in der Schweiz nicht tadellos verhalten hat; hier fällt diesbezüglich ins Gewicht, dass gegen ihn mehrere Anzeigen wegen häuslicher Gewalt sowie - wie bereits erwähnt - diverse Verlustscheine und Betreibungen vorliegen.
2.3.5 Dem Dargelegten zufolge hat der Beschwerdeführer trotz seiner Besuchskontakte zu seiner Tochter keinen Anspruch auf Aufenthalt gemäss der zu Art. 8 EMRK und <ref-law> zitierten Praxis. Es sind ausserdem keine weiteren Umstände ersichtlich oder geltend gemacht worden, die im Rahmen der Gesamtwürdigung nach Art. 50 Abs. 1 lit. b AuG zu einer anderen Beurteilung führen würden. Namentlich ist der Beschwerdeführer erst als Erwachsener in die Schweiz gelangt und hat seine prägenden Kinder- und Jugendjahre in seinem Heimatland verbracht und dort 2005 geheiratet. Auch ist er weder beruflich noch privat überdurchschnittlich integriert. Dass der Beschwerdeführer aufgrund fehlender beruflicher Qualifikationen Schwierigkeiten haben dürfte, sich bei einer Rückkehr nach Mazedonien in den dortigen Arbeitsmarkt einzugliedern, mag zutreffen, doch gilt das Gleiche auch für den hiesigen Arbeitsmarkt (Urteile 2C_1029/2011 vom 10. April 2012 E. 3.2.2; 2C_262/2010 vom 9. November 2010 E. 3.3.4).
3. 3.1 Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist.
3.2 Damit wird der Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da die Beschwerde aber nicht als aussichtslos zu bezeichnen ist und die Bedürftigkeit des Beschwerdeführer als erstellt gelten kann, was das Verwaltungsgericht auch für das vorinstanzliche Verfahren festgestellt hat, ist dem Gesuch um Gewährung der unentgeltlichen Rechtspflege unter Beiordnung des beigezogenen Rechtsanwalts zu entsprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Dem Beschwerdeführer wird für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege gewährt.
a) Es werden keine Gerichtskosten erhoben.
b) Fürsprech Jürg Walker, Olten, wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 14. Mai 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger