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.