Sachverhalt:
A. Der aus dem Kosovo stammende X._ (geb. 1981) reiste am 18. August 1990 mit seiner Mutter und einem Bruder in die Schweiz ein, wo das von der Mutter gestellte Asylgesuch abgewiesen wurde. Nachdem sich die Mutter mit einem Schweizer Bürger verheiratet hatte, erhielt X._ im Rahmen des Familiennachzugs am 12. Oktober 1993 eine Aufenthaltsbewilligung. Am 18. November 1998 wurde ihm die Niederlassungsbewilligung erteilt.
X._ führt mit der serbischen Staatsangehörigen A._ (geb. 1982), welche im Kanton Neuenburg vorläufig aufgenommen ist (Ausweis F), eine Lebensgemeinschaft, aus welcher die Kinder B._ (geb. 2008) und C._ (geb. 2009) hervorgegangen sind.
Während seines Aufenthalts in der Schweiz wurde X._ zu folgenden Strafen und Massnahmen verurteilt:
mit Strafverfügung der Jugendanwaltschaft des Kantons Solothurn vom 11. August 1999 zur Errichtung einer Erziehungshilfe wegen Raufhandels und geringfügigen Diebstahls;
mit Strafurteil des Bezirksgerichts Baden vom 15. September 2003 zu fünf Tagen Gefängnis und einer Busse von Fr. 400.-- wegen Fahrens ohne Fahrzeugausweis oder Kontrollschilder sowie ohne Haftpflichtversicherung;
mit Urteil des Obergerichts des Kantons Aargau vom 7. April 2005 zu 18 Monaten Gefängnis und einer Busse von Fr. 1'000.-- wegen gewerbsmässigen Diebstahls, mehrfacher Sachbeschädigung und mehrfachen Hausfriedensbruchs sowie Entwendung zum Gebrauch;
mit Strafbefehl des Bezirksamtes Aarau vom 14. August 2007 zu einer Busse von Fr. 1'000.-- wegen geringfügigen Diebstahls;
mit Urteil des Obergerichts des Kantons Solothurn vom 8. April 2009 zu drei Jahren Freiheitsstrafe, einer Busse von Fr. 800.-- sowie zur Anordnung einer vollzugsbegleitenden ambulanten Behandlung wegen Freiheitsberaubung und Entführung, mehrfacher Drohung, Schändung, mehrfacher Tätlichkeiten, mehrfacher sexueller Handlungen mit einem Kind, mehrfacher Übertretung des Betäubungsmittelgesetzes, mehrfacher einfacher und grober Verkehrsregelverletzung, mehrfachen Fahrens in fahrunfähigem Zustand, Überlassens eines nicht betriebssicheren Fahrzeugs, mehrfachen Fahrens ohne Fahrzeugausweis oder Kontrollschilder, mehrfachen Fahrens ohne Haftpflichtversicherung, mehrfacher missbräuchlicher Verwendung von Ausweisen oder Kontrollschildern und mehrfachen Nichtmitführens von Ausweisen;
mit Strafverfügung der Staatsanwaltschaft des Kantons Solothurn vom 21. Oktober 2009 zu 60 Tagessätzen Geldstrafe zu je Fr. 30.-- und einer Busse von Fr. 1'400.-- wegen einfacher Verkehrsregelverletzung, Führens und Überlassens eines nicht betriebssicheren Fahrzeugs, Fahrens und Fahrenlassens ohne Fahrzeugausweis, ohne Kontrollschild und ohne Haftpflichtversicherung, Nichttragens eines Schutzhelms, Hinderung einer Amtshandlung, Trunkenheit und unanständigem Benehmens;
mit Strafverfügung der Staatsanwaltschaft des Kantons Solothurn vom 23. Juli 2010 zu 10 Tagessätzen Geldstrafe zu je Fr. 60.-- und einer Busse von Fr. 700.-- wegen grober Verkehrsregelverletzung;
mit Strafverfügung der Staatsanwaltschaft des Kantons Solothurn vom 11. August 2010 zu einer Busse von Fr. 400.-- wegen Überschreitens der Höchstgeschwindigkeit.
X._ befand sich vom 24. Oktober 2005 bis zum 23. Oktober 2006 im Strafvollzug. Seit dem 21. Juni 2010 hielt er sich in der Strafanstalt Witzwil auf, wo er am 1. März 2011 in den offenen Vollzug übertreten konnte. Am 18. Mai 2012 ist X._ bedingt aus dem Strafvollzug entlassen worden.
Gegen X._ liegen zudem vier Betreibungen im Betrag von Fr. 1'912.65 sowie fünf Verlustscheine im Betrag von Fr. 3'576.05 vor. Zudem musste er von der Sozialhilfe mit insgesamt Fr. 69'759.10 unterstützt werden.
B. Mit Verfügung vom 4. November 2011 widerrief das Departement des Innern des Kantons Solothurn, vertreten durch die Abteilung Migration und Schweizer Ausweise, die Niederlassungsbewilligung von X._ und wies ihn an, die Schweiz am Tag seiner Entlassung aus dem Strafvollzug zu verlassen. Zur Begründung verwies das Departement im Wesentlichen auf die von X._ verübten Straftaten.
Eine von X._ hiergegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 23. März 2012 ab.
C. Mit Eingabe vom 26. April 2012 erhebt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 23. März 2012 sowie die Verfügung des Departements des Innern vom 4. November 2011 betreffend Widerruf der Niederlassungsbewilligung seien aufzuheben.
D. Das Verwaltungsgericht und das Departement des Innern des Kantons Solothurn beantragen, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde.
Mit Verfügung vom 1. Mai 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.
Am 20. Juni 2012 ersucht X._ um unentgeltliche Rechtspflege und -verbeiständung.
Erwägungen:
1. 1.1 Gegen kantonal letztinstanzliche Entscheide über den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (Art. 82 lit. a, Art. 83 lit. c Ziff. 2 [e contrario] und Art. 86 Abs. 1 lit. d und Abs. 2 BGG; BGE 135 II 1 E. 1.2.1 S. 4; Urteile 2C_401/2012 vom 18. September 2012 E. 1.3; 2C_478/2010 vom 17. November 2010 E. 2, nicht publ. in: BGE 137 II 10), und der Beschwerdeführer ist zur Ergreifung dieses Rechtsmittels befugt (Art. 89 BGG). Der Beschwerdeführer kann sich grundsätzlich gestützt auf den kombinierten Schutzbereich von Privat- und Familienleben auch auf Art. 8 EMRK berufen.
1.2 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG, SR 142.20) in Kraft getreten. Gemäss der Übergangsbestimmung von Art. 126 Abs. 1 AuG bleibt auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, das bisherige Recht (Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer [ANAG; in Kraft gewesen bis 31. Dezember 2007; BS 1 121]) anwendbar. Das bisherige materielle Recht ist sodann überhaupt auf alle Verfahren anwendbar, die erstinstanzlich vor Inkrafttreten des neuen Rechts eingeleitet wurden, unabhängig davon, ob sie von Amtes wegen oder auf Gesuch hin eröffnet wurden. Unter Verfahrenseröffnung versteht die Rechtsprechung in der Regel die Gewährung des rechtlichen Gehörs (Urteil 2C_7/2011 vom 25. Juli 2011 E. 2.1).
1.2.1 Nach Auffassung des Verwaltungsgerichts wie auch des Departementes des Innern des Kantons Solothurn ist für die materielle Beurteilung vorliegend noch das ANAG massgebend, da das Verfahren betreffend Widerruf der Niederlassungsbewilligung mit Erteilung des rechtlichen Gehörs am 21. Juni 2006 durch die Behörde eingeleitet worden sei (vgl. angefochtener Entscheid E. 2).
1.2.2 Dabei verkennen die Vorinstanzen, dass sich die erstmalige Gewährung des rechtlichen Gehörs noch auf ein Ausweisungsverfahren (gemäss ANAG) aufgrund der Verurteilungen bis 2006 bezog. Im vorliegenden Verfahren geht es jedoch um einen Widerruf der Niederlassungsbewilligung (gemäss AuG), der sich schwergewichtig auf die dreijährige Freiheitsstrafe gemäss Urteil des Solothurner Obergerichts vom 8. April 2009 abstützt. In Bezug auf dieses Widerrufsverfahren gewährte das Departement dem Beschwerdeführer mit Schreiben vom 19. April 2011 das rechtliche Gehör.
1.2.3 Damit sind die Voraussetzungen für die Anwendung des neuen Rechts im vorliegenden Widerrufsverfahren ohne Weiteres gegeben. Im Übrigen würde auch die Anwendung des alten Rechts im vorliegenden Fall zu keinem anderen materiellen Ergebnis führen (vgl. E. 2.3 und 2.4 hiernach).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. BGE 134 II 244 E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (BGE 133 II 249 E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (Art. 106 Abs. 2 BGG; vgl. BGE 135 II 384 E. 2.2.1 S. 389).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG bzw. Art. 105 Abs. 2 BGG). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG; vgl. BGE 135 I 143 E. 1.5 S. 146 f.).
1.5 Unzulässig ist das Rechtsmittel, soweit es sich gegen die Verfügung des Departements richtet, da diese durch das verwaltungsgerichtliche Urteil ersetzt worden ist und als mit angefochten gilt (sog. Devolutiveffekt; vgl. BGE 134 II 142 E. 1.4 S. 144; 129 II 438 E. 1 S. 441).
2. 2.1 Nach Art. 63 Abs. 1 lit. a (in Verbindung mit Art. 62 lit. b) und Art. 63 Abs. 2 AuG kann die Niederlassungsbewilligung auch nach einem - wie hier - länger als 15 Jahre dauernden ununterbrochenen und ordnungsgemässen Aufenthalt in der Schweiz widerrufen werden, wenn der Ausländer zu einer längerfristigen Freiheitsstrafe verurteilt wurde. Als längerfristig gilt eine Freiheitsstrafe von mehr als einem Jahr (BGE 135 II 377 E. 4.2 S. 379 ff.).
2.2 Ebenso ist ein Bewilligungswiderruf gemäss Art. 63 Abs. 1 lit. b und Art. 63 Abs. 2 AuG u.a. dann möglich, wenn der Ausländer in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung verstossen oder diese gefährdet hat. Dabei ist in erster Linie auf den Stellenwert des beeinträchtigten Rechtsguts abzustellen; wenn die ausländische Person durch ihre Handlungen besonders hochwertige Rechtsgüter wie namentlich die körperliche, psychische und sexuelle Integrität eines Menschen verletzt oder gefährdet hat, sind die Tatbestandsvoraussetzungen von Art. 63 Abs. 1 lit. b AuG zumeist erfüllt. Indes können auch vergleichsweise weniger gravierende Pflichtverletzungen als "schwerwiegend" im Sinne von Art. 63 Abs. 1 lit. b AuG bezeichnet werden: Ein Widerruf der Niederlassungsbewilligung ist namentlich auch dann möglich, wenn sich eine ausländische Person von strafrechtlichen Massnahmen nicht beeindrucken lässt und damit zeigt, dass sie auch zukünftig weder gewillt noch fähig ist, sich an die Rechtsordnung zu halten. Ob der Ausländer willens und in der Lage ist, sich in die hier geltende Ordnung einzufügen, kann nur anhand einer Gesamtbetrachtung seines Verhaltens beurteilt werden; auch eine Summierung von Verstössen, die für sich genommen für einen Widerruf nicht ausreichen würden, können deshalb einen Bewilligungsentzug rechtfertigen, und sogar das Bestehen von privatrechtlichen Schulden kann gegebenenfalls einen schwerwiegenden Verstoss gegen die öffentliche Sicherheit und Ordnung darstellen, wenn die Verschuldung mutwillig erfolgt ist (BGE 137 II 297 E. 3 S. 302 ff. mit Hinweisen).
2.3 Wenn ein Ausländer durch sein Verhalten einen Widerrufsgrund gesetzt hat, bleibt zu prüfen, ob diese Massnahme auch als verhältnismässig erscheint. Dabei sind namentlich die Schwere des Verschuldens, der Grad der Integration sowie die dem Betroffenen drohenden Nachteile zu berücksichtigen (BGE 135 II 377 E. 4.3 ff. S. 381 ff.; vgl. auch Art. 96 Abs. 1 AuG). Nach der Rechtsprechung des Bundesgerichts zu dieser gesetzlichen Regelung und zu den analogen früheren Bestimmungen (Art. 10 Abs. 1 lit. a und Art. 11 Abs. 3 ANAG) sind umso strengere Anforderungen an eine fremdenpolizeiliche Massnahme zu stellen, je länger ein Ausländer in der Schweiz anwesend war. Selbst bei einem Ausländer, der bereits hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat (Ausländer der zweiten Generation), sind fremdenpolizeiliche Massnahmen aber nicht ausgeschlossen; bei schweren bzw. wiederholten Straftaten, insbesondere bei Gewalt-, Sexual- und Betäubungsmitteldelikten, besteht hieran ein wesentliches öffentliches Interesse (BGE 122 II 433 E. 2c S. 436; 130 II 176 E. 4.4.2 S. 190).
2.4 Die Notwendigkeit einer Verhältnismässigkeitsprüfung ergibt sich auch aus Art. 8 Ziff. 2 EMRK: Danach ist ein Eingriff in das von Art. 8 Ziff. 1 EMRK geschützte Privat- und Familienleben dann statthaft, wenn er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung oder zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint. Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind - wie früher bei jener nach Art. 11 Abs. 3 ANAG - die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die primär betroffene Person sowie deren familiäre Situation zu berücksichtigen (BGE 135 II 377 E. 4.3 S. 381). Unter den Gesichtspunkten der Dauer der Anwesenheit sowie der persönlichen und familiären Nachteile ist es grundsätzlich angezeigt, bei Ausländern, die in der Schweiz aufgewachsen sind, von fremdenpolizeilichen Massnahmen zurückhaltend Gebrauch zu machen (vgl. Urteile des EGMR vom 18. Oktober 2006 Üner gegen die Niederlande, Nr. 46410/99, § 58 in fine; vom 22. Mai 2008 Emre gegen die Schweiz, Nr. 42034/04, § 69, sowie vom 23. Juni 2008 Maslov gegen Österreich, Nr. 1638/03, § 74 f.).
3. 3.1 Der Beschwerdeführer wurde wegen verschiedener schwerer Delikte insgesamt zu über viereinhalb Jahren Freiheitsstrafe verurteilt, womit er einen Widerrufsgrund im Sinne von Art. 63 Abs. 1 lit. a (in Verbindung mit Art. 62 lit. b) AuG gesetzt hat. Ob das Verhalten des Beschwerdeführers zugleich als schwerwiegender Verstoss gegen die öffentliche Sicherheit und Ordnung im Sinne von Art. 63 Abs. 1 lit. b AuG zu werten ist, bedarf somit keiner näheren Betrachtung, weil dieser Widerrufsgrund in der vorliegenden Konstellation ohnehin nur subsidiär zur Anwendung kommt, wenn es an den Voraussetzungen für einen Widerruf in Anwendung von Art. 63 Abs. 1 lit. a (in Verbindung mit Art. 62 lit. b) AuG gebricht (vgl. BGE 135 II 377 E. 4.2 S. 381).
3.2 Die kantonalen Behörden haben sodann die für die Beurteilung des Widerrufs der Niederlassungsbewilligung relevanten Kriterien zutreffend dargelegt. Der Beschwerdeführer wurde unter anderem wegen Schändung, Freiheitsberaubung, Entführung, sexueller Handlungen mit einem Kind und gewerbsmässig begangenen Diebstahls verurteilt. Gemäss dem Urteil des Obergerichts des Kantons Solothurn hat der Beschwerdeführer eine bemerkenswerte kriminelle Energie an den Tag gelegt und es trifft ihn ein grosses Verschulden. Aus dem blossen Hinweis, es habe sich beim schwersten Delikt um ein Beziehungsdelikt gehandelt, welches nun acht Jahre zurückliege, und er habe an einer schizoiden Störung gelitten, kann der Beschwerdeführer unter diesen Umständen nichts zu seinen Gunsten ableiten.
Angesichts der Schwere der mehrfach begangenen Delikte vermag an dieser Einschätzung auch nichts zu ändern, dass gemäss Beurteilung der konkordatlichen Fachkommission zur Beurteilung der Gemeingefahr von Straftätern (KoFako) vom 25. Mai 2011 der Beschwerdeführer nicht als gemeingefährlich beurteilt wird; immerhin hält es die KoFako für möglich, dass der Beschwerdeführer in einer neuen Partnerschaft unter Umständen erneut mit ähnlichem deliktischen Verhalten auftreten könnte. Zudem führt der Therapiebericht der Forensisch-Psychiatrischen Dienste der Universität Bern vom 17. Mai 2011 aus, die Fachkommission erkenne kaum soziale Kompetenzen, welche sich deliktspräventiv auswirken würden (vgl. angefochtener Entscheid E. 5a). Unter diesen Umständen kann dem Beschwerdeführer nicht gefolgt werden, wenn er ausführt, die Rückfallgefahr sei "weitgehend gebannt".
Abgesehen davon muss bei Ausländern, welche sich - wie der Beschwerdeführer - nicht auf das Freizügigkeitsabkommen (FZA; SR 0.142.112.681) berufen können, beim Fernhalteinteresse nicht allein auf das Kriterium der Rückfallgefahr und -wahrscheinlichkeit abgestellt werden, sondern es darf auch generalpräventiven Gesichtspunkten Rechnung getragen werden (Urteile 2C_28/2010 vom 25. März 2011 E. 2.3, 2C_466/2009 vom 13. Januar 2010 E. 5.2; je mit Hinweisen). Zudem verfolgt das Bundesgericht insbesondere auch bei Delikten gegen die körperliche und sexuelle Integrität eine strenge Praxis (BGE 125 II 521 E. 4.a/aa S. 526 f.; 122 II 433 E. 2.c S. 436 f.): Selbst ein relativ geringes Rückfallrisiko muss in diesen Fällen nicht hingenommen werden.
Mit der Vorinstanz ist damit von einem grossen öffentlichen Interesse daran auszugehen, dem Beschwerdeführer die weitere Anwesenheit in der Schweiz zu verwehren.
3.3 Die gegenläufigen privaten Interessen des Beschwerdeführers am Verbleib in der Schweiz fallen demgegenüber weniger schwer ins Gewicht.
Der Beschwerdeführer reiste bereits 1990 im Alter von neun Jahren in die Schweiz ein und lebt - seit der Legalisierung seines Aufenthalts 1993 - seit 19 Jahren im Land. Davon abzuziehen ist freilich die Zeit (knapp drei Jahre), in der er sich im Strafvollzug befunden hat. Der Vorinstanz ist insgesamt zuzustimmen, dass der Beschwerdeführer aufgrund des langen Aufenthalts und der familiären Bande stark mit der Schweiz verbunden ist. Hingegen hat der Beschwerdeführer keine Ausbildung abgeschlossen und musste während längerer Zeit von der Sozialhilfe unterstützt werden. Es ist ihm - auch bedingt durch seine Delinquenz und den sich daraus ergebenden Strafvollzug - nicht gelungen, sich wirtschaftlich in der Schweiz zu integrieren. Insgesamt ist festzuhalten, dass der Grad der Integration in die schweizerische Gesellschaft nicht mit seiner relativ langen Aufenthaltsdauer in der Schweiz korrespondiert. Erschwerend kommt hinzu, dass sich der Beschwerdeführer auch weder durch die Beziehungen zu seinen Familienangehörigen noch durch Verurteilungen hat davon abhalten lassen, weitere Delikte zu begehen.
Dem Beschwerdeführer ist zwar insofern zuzustimmen, dass der Widerruf der Niederlassungsbewilligung eines Ausländers, der schon seit langer Zeit in der Schweiz lebt, nur mit Zurückhaltung angeordnet werden soll. Jedoch ist ein solcher bei Gewalt- und Sexualdelikten bzw. wiederholter schwerer Straffälligkeit selbst dann keineswegs ausgeschlossen, wenn ein Ausländer hier geboren ist und sein ganzes bisheriges Leben in der Schweiz verbracht hat (vgl. E. 2.3 hiervor). Umso mehr trifft dies auf den Beschwerdeführer zu, der die ersten neun Jahre seines Lebens im Kosovo verbracht hat.
Im Übrigen ist davon auszugehen, dass ihm Kultur und Gepflogenheiten seines Heimatlandes durch sein Elternhaus vermittelt worden und somit nicht gänzlich unvertraut sind. Insgesamt erscheint eine Reintegration - trotz gewisser Schwierigkeiten - als möglich und ist mit keiner unzumutbaren Härte verbunden. Es mag zutreffen, dass dem Beschwerdeführer in seiner Heimat nicht die gleichen beruflichen Perspektiven offenstehen wie in der Schweiz. Diese Folge ist indessen seinem kriminellen Verhalten zuzuschreiben und insofern hinzunehmen.
3.4 Soweit sich der Beschwerdeführer im Weiteren sinngemäss auf Art. 8 Ziff. 1 EMRK (Schutz des Privat- und Familienlebens) beruft, kann ihm - abgesehen davon, dass es sich als fraglich erweist, ob die Rügen überhaupt den Begründungsanforderungen (vgl. E. 1.3 hiervor) zu genügen vermögen - nicht gefolgt werden.
Zwar kann das in Art. 8 Ziff. 1 EMRK verankerte Recht auf Achtung des Privat- und Familienlebens verletzt sein, wenn einem Ausländer, dessen Familienangehörige hier weilen, die Anwesenheit untersagt und damit das Familienleben vereitelt wird. Das geschützte Familienleben beschränkt sich in erster Linie auf die Kernfamilie, d.h. die Gemeinschaft der Ehegatten mit ihren minderjährigen Kindern (vgl. BGE 135 I 143 E. 1.3.2 S. 146 mit Hinweisen). In den Schutzbereich von Art. 8 EMRK fallen aber auch nicht rechtlich begründete familiäre Verhältnisse, sofern eine genügend nahe, echte und tatsächlich gelebte Beziehung besteht; entscheidend ist die Qualität des Familienlebens und nicht dessen rechtliche Begründung (BGE 135 I 143 E. 3.1 S. 148).
Der Beschwerdeführer ist gemäss den Feststellungen der Vorinstanz seit mehreren Jahren mit einer serbischen Staatsangehörigen liiert, hat mit ihr zwei Kinder und beabsichtigt offenbar, bald zu heiraten. Allerdings verfügen die Verlobte und die beiden Kinder des Beschwerdeführers über keinen gesicherten Aufenthaltsstatus in der Schweiz (Ausweis F: vorläufig aufgenommene Ausländerin). Ob die Beziehung als hinreichend stabil betrachtet werden kann, um dem Beschwerdeführer einen Bewilligungsanspruch gestützt auf Art. 8 EMRK einzuräumen, erscheint aufgrund der Rechtsprechung (vgl. BGE 135 I 43 E. 3.1 S. 148) und gerade auch im Hinblick auf den unsicheren Aufenthaltsstatus als zweifelhaft. Die Frage kann jedoch dahingestellt bleiben, da ein Eingriff in das geschützte Familienleben nach Art. 8 Abs. 2 EMRK angesichts der Schwere der noch nicht weit zurückliegenden Straftätigkeit ohnehin verhältnismässig wäre. Zudem ist die Verlobte des Beschwerdeführers ebenfalls im Kosovo geboren und erst im Alter von elf Jahren in die Schweiz eingereist. Sie ist hier zwar integriert und es würde ihr gewiss schwer fallen, mit dem Beschwerdeführer auszureisen. Indessen wäre ihr eine Ausreise in den Kosovo nicht geradezu unzumutbar. Zu berücksichtigen ist auch, dass sie nicht ohne Weiteres damit rechnen konnte, ihre Beziehung mit dem Beschwerdeführer, über dessen "Vorleben" (vgl. Beschwerde Ziff. 10) sie informiert ist, zukünftig in der Schweiz leben zu können.
3.5 Mit Blick auf die begangenen Delikte und die nicht hinzunehmende Rückfallgefahr bestehen ordnungs- und sicherheitspolitische Gründe, welche die privaten Interessen an einem weiteren Verbleib des Beschwerdeführers überwiegen und den Widerruf der Bewilligung bzw. einen Eingriff in das Recht auf Achtung des Familienlebens im Sinne von Art. 8 Abs. 2 EMRK rechtfertigen. Das angefochtene Urteil ist bundesrechts- und konventionskonform.
4. 4.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Da dem Gesuch um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung vor Bundesgericht infolge Aussichtslosigkeit der Rechtsbegehren nicht entsprochen werden kann (Art. 64 BGG), hat der unterliegende Beschwerdeführer grundsätzlich die bundesgerichtlichen Kosten zu tragen. Der finanziellen Lage des Beschwerdeführers wird indessen bei der Bemessung der Gerichtsgebühr Rechnung getragen.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 20. Dezember 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger