Sachverhalt:
A. Der aus dem ehemaligen Serbien und Montenegro stammende X._ (geb. 1978) reiste am 13. Dezember 1995 illegal in die Schweiz ein und stellte ein Asylgesuch. Das Bundesamt für Flüchtlinge (heute Bundesamt für Migration) lehnte das Gesuch mit Verfügung vom 22. Mai 1996 ab und wies X._ aus der Schweiz weg. Trotzdem verblieb X._ in der Schweiz und kam auch der Aufforderung vom 20. November 1997, das Land bis zum 30. Juli 1998 zu verlassen, nicht nach. Am 30. Juni 1999 wurde er im Rahmen der durch den Bundesrat am 7. April 1999 beschlossenen Kollektivaufnahme vorläufig aufgenommen. Nach der Aufhebung der vorläufigen Aufnahme, ordnete die Asylbehörde des Kantons Waadt die Ausreise von X._ per 31. Juli 2000 an, worauf dieser untertauchte. Am 28. August 2000 wurde er von der Polizei aufgegriffen und reiste am 29. August 2000 kontrolliert nach Pristina aus.
Nach erneuter illegaler Einreise in die Schweiz am 26. Mai 2002 wurde er von der Polizei festgenommen und am 8. Juni 2002 erfolgte seine Rückführung nach Pristina. Das Bundesamt für Flüchtlinge verfügte am 27. Juni 2002 über X._ eine Einreisesperre bis zum 26. Juni 2005.
Nachdem er im September 2003 zum dritten Mal illegal in die Schweiz eingereist war, wurde er am 8. Oktober 2003 von der Bahnpolizei in A._ aufgegriffen.
B. Am 17. Januar 2005 heiratete X._ in B._ die Schweizer Bürgerin Y._ (geb. 1972), die bereits zwei Kinder aus zwei früheren Beziehungen hatte und von Juli 1999 bis Februar 2005 mit insgesamt über Fr. 69'000.-- sozialhilferechtlich unterstützt werden musste. Obwohl vorerst Verdacht auf Scheinehe bestand, wurde X._ mit Verfügung vom 19. Mai 2005 die Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau erteilt. Im November 2005 wusste die Ehefrau nicht, wo sich X._ aufhielt.
In der Folge arbeitete der Ehemann in der Westschweiz und kehrte angeblich jeweils am Wochenende bzw. ein- bis dreimal im Monat kurz nach B._ zu seiner Ehefrau zurück. Am 31. Januar 2006 liess er die zusammen mit seiner Halbschwester in C._ gegründete D._ Sàrl im Handelsregister eintragen.
Am 3. Januar 2007 gebar Y._ den Sohn E._. Das Richteramt F._ stellte am 7. Juli 2007 fest, dass X._ nicht der Vater dieses Kindes ist. G._, der vom 1. Oktober 2006 bis zum 15. Oktober 2008 bei Y._ wohnte, anerkannte das Kind. Obwohl die eheliche Beziehung damals offensichtlich nicht gelebt wurde, unterstützte X._ seine Ehefrau, die seit August 2007 über kein Einkommen verfügte, mit monatlich Fr. 1'500.--. An der am 12. März 2008 vorgenommenen Befragung betreffend die aktuelle Ehesituation machten die Ehegatten zahlreiche widersprüchliche Aussagen. Mit Schreiben vom 6. September 2008 erklärte X._ dem Departement des Innern, er sei mit seiner Ehefrau eine Zeit lang nicht mehr zusammen gewesen, jedoch würden sie die eheliche Beziehung seit dem 1. März 2008 wieder leben; zudem halte er sich jedes Wochenende in B._ auf. G._, der auch nach der angeblichen Wiederaufnahme der ehelichen Beziehung weiter bei Y._ wohnte, teilte im Oktober 2008 der Migrationsbehörde unaufgefordert mit, X._ verbringe nicht jedes Wochenende in B._ und dann nur aus Angst vor einer Polizeikontrolle. Zudem erwarte Y._ erneut ein Kind, das wiederum von ihm und nicht vom Ehemann stamme. Im Rahmen des rechtlichen Gehörs betreffend Nichtverlängerung der Aufenthaltsbewilligung machten die Ehegatten X._/Y._ mit Schreiben vom 1. November 2008 geltend, die Aussagen von G._ entsprächen nicht der Wahrheit, das Kind sei geplant gewesen und stamme vom Ehemann. Dieser bemühe sich nun um Aufträge im Kanton Solothurn und wolle nach der Geburt des Kindes ganz zu seiner Ehegattin ziehen. Im Übrigen beabsichtige er, sobald er über die Niederlassungsbewilligung verfüge, das Haus zu kaufen, in dem seine Ehegattin wohne. Am 8. Mai 2009 gebar die Ehefrau die Tochter H._.
C. Mit Verfügung vom 18. Mai 2009 verweigerte das Departement des Innern, Abteilung Ausländerfragen, des Kantons Solothurn die Verlängerung der Aufenthaltsbewilligung von X._ mit der Begründung, der Aufenthaltszweck sei weggefallen, und wies den Betroffenen an, die Schweiz bis zum 31. August 2009 zu verlassen. Die dagegen erhobene Beschwerde lehnte das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 27. August 2009 ab. Es bestätigte die Nichtverlängerung mit der Begründung die Voraussetzungen für den Widerruf der Aufenthaltsbewilligung wegen wissentlicher falscher Angaben bzw. Verschweigens wesentlicher Tatsachen seien erfüllt.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. September 2009 beantragt X._, das Urteil des Verwaltungsgerichts vom 27. August 2009 sowie die Verfügung des Departement des Innern vom 18. Mai 2009 aufzuheben und die Aufenthaltsbewilligung zu verlängern. Zudem stellt er das Begehren, der Beschwerde die aufschiebende Wirkung zuzuerkennen.
Das Verwaltungsgericht des Kantons Solothurn beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Das Departement des Innern des Kantons Solothurn, Abteilung Ausländerfragen, und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.
E. Mit Verfügung vom 5. Oktober 2009 hat der Präsident der öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde aufschiebende Wirkung zuerkannt.
F. Nach Ablauf der Beschwerdefrist haben X._ sowie dessen Ehefrau beim Bundesgericht zusätzliche Eingaben eingereicht.
Erwägungen:
1. 1.1 Am 1. Januar 2008 ist das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) in Kraft getreten, womit das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) aufgehoben wurde.
Die Aufenthaltsbewilligung des Beschwerdeführers wurde letztmals am 31. Januar 2007 verlängert und ist im Januar 2008 abgelaufen. Gegenstand des kantonalen sowie des vorliegenden Verfahrens ist somit die Verlängerung der fraglichen Aufenthaltsbewilligung. Entgegen der Auffassung des Beschwerdeführers sind die Bestimmungen des neuen Ausländergesetzes anwendbar, da das Gesuch um Verlängerung der Bewilligung am 20. Januar 2008 und damit nach Inkrafttreten des Ausländergesetzes gestellt wurde (Art. 126 Abs. 1 a contrario AuG).
1.2 Gemäss Art. 42 Abs. 1 AuG haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Das Erfordernis des Zusammenwohnens besteht nicht, wenn für getrennte Wohnorte wichtige Gründe geltend gemacht werden und die Familiengemeinschaft weiter besteht (Art. 49 AuG).
Der Beschwerdeführer beruft sich sinngemäss auf diese Anspruchsgrundlage und behauptet, die Voraussetzungen hierfür seien erfüllt. Diese Behauptung bedarf näherer Prüfung, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist (Art. 83 lit. c Ziff. 2 BGG a contrario). Ob die Eheleute zusammenwohnen oder auf dieses Erfordernis gemäss Art. 49 AuG ausnahmsweise zu verzichten ist, kann für die Eintretensfrage offen bleiben.
Nicht eingetreten werden kann jedoch auf die Beschwerde, soweit die Aufhebung der Verfügung des Departements des Innern vom 18. Mai 2009 beantragt wird. Diese ist durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gilt inhaltlich als mitangefochten (BGE 134 II 142 E. 1.4 S. 144).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (vgl. BGE 135 III 397 E. 1.4 S. 400). Hinsichtlich der Verletzung von Grundrechten gilt indessen eine qualifizierte Rügepflicht (Art. 106 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.2 S. 254). Soweit vorliegend bloss sinngemäss eine Verletzung des rechtlichen Gehörs sowie ein Verstoss gegen das Willkürverbot geltend gemacht wird, kann wegen ungenügender Begründung auf die Beschwerde nicht eingetreten werden.
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 105 Abs. 2 bzw. Art. 97 Abs. 1 BGG). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 BGG), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweist (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG).
Die Mahnung vom 15. September 2009 sowie das nachgereichte Schreiben des Vermieters vom 9. Oktober 2009 sind als sog. "echte" Noven unbeachtlich (BGE 133 IV 342 E. 2.1 mit Hinweisen). Die verschiedenen nach Ablauf der Beschwerdefrist unaufgefordert eingereichten Eingaben können nicht berücksichtigt werden; sie wären aber ohnehin nicht geeignet, am Ausgang des Verfahrens etwas zu ändern.
2. 2.1 Gemäss den für das Bundesgericht verbindlichen (Art. 105 BGG) Feststellungen der Vorinstanz besteht die Ehe des Beschwerdeführers seit langem nur noch formell. Hinweise darauf, dass die Feststellungen des Verwaltungsgerichts des Kantons Solothurn zum Sachverhalt offensichtlich unrichtig wären, sind nicht ersichtlich und gehen namentlich auch nicht aus den Vorbringen des Beschwerdeführers hervor.
Unbestrittenermassen haben sich die Ehegatten kurz nach der Heirat getrennt. Der Beschwerdeführer ist seit anfangs 2006 Inhaber einer Firma in C._ und kehrt angeblich wegen seiner beruflichen Tätigkeit nicht täglich an den ehelichen Wohnort im Kanton Solothurn (B._) zurück, wo er seit der Heirat angemeldet ist. Die Ehefrau lebte in der Folge über längere Zeit mit ihrem neuen Partner zusammen und hatte mit ihm das 2007 geborene Kind E._. Dass seine Ehegattin eine Beziehung zu einem andern Mann pflegte, kümmerte den Beschwerdeführer nicht. Es fällt zudem auf, dass er keinerlei Anstrengungen zur Wiederherstellung der ehelichen Gemeinschaft unternommen hat. In den Akten finden sich auch keine Anhaltspunkte dafür, dass sich der Beschwerdeführer um eine Anstellung in der Nähe des Wohnorts der Ehegattin bemüht bzw. ernsthaft eine Wohnung für die Familie im Raum K._ gesucht hätte.
Zwar behaupten die Ehegatten, im März 2008 hätten sie die eheliche Beziehung wieder aufgenommen. Dies ist indessen schon deshalb wenig glaubhaft, weil der Freund und Vater des dritten Kindes der Ehegattin weiterhin bei ihr wohnte und dies den Beschwerdeführer nicht störte. Wer der leibliche Vater des vierten Kindes der Ehegattin ist, steht nicht fest. Immerhin fällt auf, dass die Kindsmutter im Zeitraum der Zeugung des Kindes mit ihrem Freund, der sich als dessen Vater erachtet und bereits Vater ihres Sohnes E._ ist, und nicht mit dem Beschwerdeführer zusammenlebte, der zudem zu jener Zeit mehrere Wochen im Ausland verbrachte. Selbst wenn aber der Beschwerdeführer der leibliche Vater der anfangs Mai 2009 geborenen Tochter sein sollte, vermöchte dies allein unter den vorliegenden Umständen jedenfalls noch nicht den Nachweis weder für ein eheliches Zusammenleben noch für das Bestehen einer Ehegemeinschaft erbringen.
Vielmehr sprechen zahlreiche weitere Indizien gegen das Vorliegen einer ehelichen Beziehung. Die angeblichen wöchentlichen Besuche des Beschwerdeführers bei seiner Ehegattin dauern jeweils bloss 24 Stunden, wobei die Ehefrau unbestrittenermassen an verschiedenen Wochenenden Zeit beim Vater des Sohnes E._ verbringt, weil sie das Kind nicht allein mit ihm lassen will. Die Eheleute beherrschen keine gemeinsame Sprache, kennen die gegenseitigen Verwandten nicht und haben noch nie gemeinsame Ferien verbracht. Der Beschwerdeführer reist jedoch allein mehrmals pro Jahr ferienhalber in sein Heimatland. Weiter hat er offensichtlich kaum Kontakt zu den Kindern seiner Ehefrau. Zumindest befremdend erscheint, dass die Ehegattin die Adresse, an der sich ihr Ehegatte unter der Woche aufhält, nicht angeben konnte. Der Beschwerdeführer seinerseits wusste nichts von der Kündigung der Familienwohnung in B._ und vorerst auch nichts vom angeblich von ihm zusammen mit seiner Schwiegermutter geplanten Kauf des Wohnhauses. Im Übrigen ist die Ehefrau, die seit 2007 nicht mehr arbeitet, auf die monatlichen Unterstützungsleistungen des Beschwerdeführers (in Höhe von vorerst Fr. 1'500.-- bzw. Fr. 2000.-- und nach der Geburt des vierten Kindes in Höhe von Fr. 2'500.-- plus Kinderzulagen für drei Kinder) angewiesen, weshalb sie an seinem weiteren Verbleib ein gewichtiges finanzielles Interesse hat, umso mehr als sich der Beschwerdeführer am Kauf des Wohnhauses beteiligen soll. Dies vermag sowohl ihre Bereitschaft, die inhaltsleere Ehe über Jahre formell aufrecht zu erhalten, als auch ihre Bemühungen, das Bestehen einer ehelichen Beziehung vorzutäuschen, zu erklären. Unter den vorliegenden Umständen durfte die Vorinstanz in vorweggenommener Beweiswürdigung ohne Weiteres auf die Anhörung der Schwiegermutter sowie weiterer Personen verzichten (vgl. BGE 131 I 153 E. 3 S. 157; 130 II 425 E. 2.1 S. 428 f.; je mit Hinweisen). Da der beabsichtigte Kauf des Wohnhauses nicht entscheidrelevant ist, waren diesbezügliche zusätzliche Auskünfte zum Vornherein überflüssig. Weitere Ausführungen erübrigen sich; es genügt auf die Erwägungen im angefochtenen Urteil zu verweisen.
2.2 Bei gesamthafter Betrachtung aller Indizien musste sich der Schluss aufdrängen, dass weder ein eheliches Zusammenleben noch eine echte eheliche Gemeinschaft bestanden. Ob wichtige Gründe im Sinne von Art. 49 AuG für getrennte Wohnorte vorliegen, kann somit offen gelassen werden, da es - wie erwähnt - bereits an der zusätzlich erforderlichen Ehegemeinschaft fehlt. Der Beschwerdeführer hat daher keinen Anwesenheitsanspruch mehr gestützt auf Art. 42 AuG und zwar auch nicht in Verbindung mit Art. 49 AuG.
3. 3.1 Dass er nach Art. 50 Abs. 1 AuG weiter Anspruch auf Verlängerung der Aufenthaltsbewilligung hätte, macht der Beschwerdeführer zu Recht nicht geltend. Die Voraussetzung der dreijährigen Mindestdauer der Ehegemeinschaft (lit. a) ist offensichtlich nicht erfüllt und wichtige persönliche Gründe, die einen weiteren Aufenthalt in der Schweiz erforderlich machten (lit. b), sind nicht ersichtlich.
3.2 Selbst wenn der Beschwerdeführer der leibliche Vater des im Mai 2009 geborenen Kindes der Ehegattin sein sollte, könnte er aus diesem Umstand kein Anwesenheitsrecht ableiten (vgl. BGE 130 II 281 E. 3.1 S. 285 f.). Das Kind lebt seit der Geburt bei seiner Mutter, zu der der Beschwerdeführer nur beschränkt Kontakt hat. Dass er trotzdem eine tatsächlich gelebte, besonders enge Beziehung zum Kind pflegt, wird auch vom Beschwerdeführer nicht behauptet.
4. 4.1 Die Verweigerung der Verlängerung der Aufenthaltsbewilligung verstösst somit nicht gegen Bundesrecht. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Dem Verfahrensausgang entsprechend sind die Gerichtskosten (Art. 65 BGG) dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 Satz 1 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern, Abteilung Ausländerfragen, und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 14. April 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs