Sachverhalt: A. X._ (geboren 1972) ist Staatsangehöriger von Bangladesch. Er reiste am 31. Oktober 2003 in die Schweiz ein und stellte ein Asylgesuch, welches das Bundesamt für Migration mit Entscheid vom 12. November 2003 abwies. Eine dagegen erhobene Beschwerde wies die damals zuständige Asylrekurskommission am 26. Februar 2004 ab. In der Folge setzte das Bundesamt für Migration X._ eine Ausreisefrist bis 30. April 2004; dieser befolgte die Aufforderung zur Ausreise nicht. Am 2. Juli 2004 heiratete X._ die dominikanische Staatsangehörige Y._ (geboren 1973), welche über eine Niederlassungsbewilligung verfügt. Auf Gesuch hin erteilte das Ausländeramt des Kantons St. Gallen X._ am 11. Oktober 2005 eine Aufenthaltsbewilligung im Rahmen des Familiennachzugs. B. Nach Einleitung von Ermittlungen wegen des Verdachts einer Scheinehe wies das Ausländeramt am 17. März 2008 das im Oktober 2007 eingereichte Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung ab. Zur Begründung wurde vorgebracht, es liege eine Scheinehe vor. Dagegen erhob X._ Rekurs beim Sicherheits- und Justizdepartement des Kantons St. Gallen, welches mit Entscheid vom 4. Juli 2008 den Rekurs abwies. Mit Urteil vom 14. Oktober 2008 wies das Verwaltungsgericht des Kantons St. Gallen die gegen diesen Entscheid erhobene Beschwerde ab. C. Mit Eingabe vom 19. November 2008 führt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt, das Urteil der Vorinstanz vom 14. Oktober 2008 sei aufzuheben und es sei ihm die Aufenthaltsbewilligung zu erteilen. Gerügt wird die Verletzung des Anspruchs auf rechtliches Gehör sowie eine unrichtige Feststellung des Sachverhalts. Sodann ersucht er um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. D. Das kantonale Ausländeramt hat sich nicht vernehmen lassen. Das Sicherheits- und Justizdepartement und das Verwaltungsgericht des Kantons St. Gallen sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde. 