Sachverhalt:
A. X._ (geb. 1952), Staatsangehöriger von Bosnien und Herzegowina, reiste 1982 in die Schweiz ein und erhielt eine Jahresaufenthaltsbewilligung. 1984 folgten ihm seine Ehefrau Y._ und der gemeinsame Sohn A._ (geb. 1979) im Rahmen des Familiennachzugs in die Schweiz.
Am 6. November 1984 wurde X._ vom Kreisgericht Fünf Dörfer wegen Gehilfenschaft zu Diebstahl mit drei Monaten Gefängnis bedingt bestraft. Am 2. Januar 1986 sprach die Fremdenpolizei des Kantons St. Gallen (heute: Ausländeramt) gegen ihn eine Verwarnung aus. Die Aufenthaltsbewilligung wurde widerrufen und es wurde ihm eine sogenannte Toleranzbewilligung (Ausweis D) erteilt. In der Folge erhielt er dann wieder eine Aufenthaltsbewilligung. Im Jahre 1988 kam der Sohn B._ zur Welt. 1992 wurde das Gesuch von X._ um Erteilung einer Niederlassungsbewilligung abgewiesen.
Die Eheleute X._ und Y._ liessen sich 1994 scheiden. Am 18. November 1994 wies das Ausländeramt das erneute Gesuch von X._ um Erteilung der Niederlassungsbewilligung ab mit der Begründung, der Gesuchsteller komme seinen finanziellen Verpflichtungen nicht ordnungsgemäss nach.
B. In der Folge wurde X._ wiederholt straffällig: Am 12. April 1995 wurde er wegen Geschwindigkeitsüberschreitung mit Fr. 400.-- gebüsst. Mit Strafbescheid vom 23. Oktober 1995 wurde er wegen Widerhandlung gegen die Verordnung über den Erwerb und das Tragen von Schusswaffen durch jugoslawische Staatsangehörige mit zehn Tagen Gefängnis und Fr. 400.-- Busse bestraft. Am 15. September 1998 wurde er mit Fr. 1'000.-- gebüsst, weil er um hohe Geldbeträge gespielt hatte. Am 21. Oktober 1998 wies das Ausländeramt ein erneutes Gesuch von X._ um Erteilung der Niederlassungsbewilligung ab.
In der Nacht vom 28. auf den 29. Dezember 1998 schoss X._ im Verlauf einer Auseinandersetzung zwischen verschiedenen Personen aus dem ehemaligen Jugoslawien einem Widersacher mit einer Faustfeuerwaffe nach und verletzte ihn mit einem Streifschuss im Lendenbereich. Das Kreisgericht St. Gallen erklärte X._ mit Urteil vom 12./17. Februar 2003 der versuchten vorsätzlichen Tötung, des Angriffs, der Widerhandlung gegen das Waffengesetz sowie der mehrfachen groben Verletzung der Verkehrsregeln schuldig und verurteilte ihn zu 6 Jahren und 9 Monaten Zuchthaus. Ferner verwies es ihn für 5 Jahre des Landes, unter Gewährung des bedingten Strafvollzugs mit einer Probezeit von 5 Jahren. Auf Berufung hin sprach ihn das Kantonsgericht St. Gallen mit Urteil vom 30. Juni 2004 der versuchten vorsätzlichen Tötung, der Widerhandlung gegen das Waffengesetz sowie der mehrfachen groben Verletzung der Verkehrsregeln schuldig und verurteilte ihn zu 5 1⁄2 Jahren Zuchthaus. Von der Anklage der einfachen Verletzung von Verkehrsregeln und des Angriffs sprach es ihn frei. Die bedingte Landesverweisung wurde bestätigt. Am 15. November 2004 trat X._ in den Strafvollzug ein. Mit Urteil vom 15. Dezember 2004 (6P.140/2004, 6S.385/2004) wies das Bundesgericht die von X._ gegen den Entscheid des Kantonsgerichts eingereichten Beschwerden ab, soweit es darauf eintrat.
C. Am 10. März 2006 heiratete X._ eine Schweizer Bürgerin, die ursprünglich ebenfalls aus Bosnien und Herzegowina stammt.
X._ beging am 4. November 2007 auf der Rückfahrt vom Urlaub in die Strafanstalt eine massive Geschwindigkeitsüberschreitung um rund 40 km/h auf der Autobahn.
Mit Verfügung vom 28. November 2007 verweigerte das Ausländeramt des Kantons St. Gallen die Verlängerung der Aufenthaltsbewilligung von X._. Dagegen erhob X._ erfolglos Rekurs an das Sicherheits- und Justizdepartement und sodann Beschwerde an das Verwaltungsgericht des Kantons St. Gallen. Im April 2008 wurde er bedingt aus dem Strafvollzug entlassen.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 30. Juni 2008 beantragt X._, den Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 22. Mai 2008 sowie den Entscheid des Sicherheits- und Justizdepartements "vom 4. Februar 2008 vom 27. Juli 2007" aufzuheben und seine Aufenthaltsbewilligung zu verlängern.
Das Verwaltungsgericht und das Sicherheits- und Justizdepartement des Kantons St. Gallen sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Kantonale Ausländeramt St. Gallen liess sich nicht vernehmen.

Erwägungen:
1. 1.1 Nach <ref-law> ist die Beschwerde in öffentlichrechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts ausgeschlossen gegen die Erteilung oder Verweigerung von Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
1.2 Gemäss Art. 126 Abs. 1 des neuen Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20), welches am 1. Januar 2008 in Kraft getreten ist, bleibt für Gesuche, die vor diesem Zeitpunkt gestellt worden sind, das bisherige Recht anwendbar. Das muss auch gelten für Verfahren, die von Amtes wegen noch unter altem Recht eingeleitet worden sind, wie dies hier der Fall war.
1.3 Der Beschwerdeführer, der mit einer Schweizer Bürgerin verheiratet ist, besitzt gemäss Art. 7 Abs. 1 des hier noch massgebenden (E. 1.2) Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer grundsätzlich einen Rechtsanspruch auf Verlängerung der Aufenthaltsbewilligung. Zusätzlich kann er sich auch auf das in Art. 8 Ziff. 1 EMRK bzw. in <ref-law> garantierte Recht auf Achtung des Familienlebens berufen. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig. Soweit damit auch die Aufhebung des Entscheids des Sicherheits- und Justizdepartements vom 4. Februar 2008 und allenfalls der Verfügung des Ausländeramts (auf was sich das Datum 27. Juli 2007 bezieht, ist nicht klar) beantragt wird, kann auf die Beschwerde jedoch nicht eingetreten werden (<ref-law>).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig erfolgt ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (<ref-law>), setzt zudem voraus, dass die Behebung des Mangels sich für den Ausgang des Verfahrens als entscheidend erweisen kann (<ref-law>). 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>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 2.2 S. 246). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Gemäss Art. 7 Abs. 1 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers - wie erwähnt - grundsätzlich Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (erster Satz). Der Anspruch erlischt, wenn ein Ausweisungsgrund vorliegt (dritter Satz).
2.2 Der Ausländer kann aus der Schweiz unter anderem ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde (Art. 10 Abs. 1 lit. a ANAG). Die Ausweisung soll aber nur verfügt werden, wenn sie nach den gesamten Umständen "angemessen", d.h. verhältnismässig, erscheint (Art. 11 Abs. 3 ANAG). Hierbei sind vor allem die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer). Eine vergleichbare Interessenabwägung setzt im Übrigen gemäss Art. 8 Ziff. 2 EMRK auch ein Eingriff in das Recht auf Achtung des Familienlebens voraus (<ref-ruling> E. 4.1 S. 22 f.).
Ob die Ausweisung gemäss den massgeblichen Bestimmungen verhältnismässig ist, ist eine Rechtsfrage, die vom Bundesgericht im vorliegenden Beschwerdeverfahren frei geprüft wird. Dem Bundesgericht ist es jedoch verwehrt, sein eigenes Ermessen - im Sinne einer Überprüfung der Zweckmässigkeit der Ausweisung - an die Stelle des Ermessens der zuständigen kantonalen Behörde zu setzen (<ref-ruling> E. 5.1 S. 208 mit Hinweis).
2.3 Ausgangspunkt für die ausländerrechtliche Interessenabwägung gemäss Art. 11 Abs. 3 ANAG ist das Verschulden des Ausländers. Dieses findet vorab im vom Strafrichter verhängten Strafmass seinen Ausdruck. Dabei sind umso strengere Anforderungen an die Schwere des strafrechtlichen Verschuldens zu stellen, je länger ein Ausländer in der Schweiz gelebt hat. Zu berücksichtigen ist auch, in welchem Alter der Ausländer in die Schweiz eingereist ist. 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"), ist bei Gewalt-, Sexual- oder Betäubungsmitteldelikten bzw. wiederholter Straffälligkeit eine Ausweisung jedoch nicht ausgeschlossen (<ref-ruling> E. 4.4.2 S. 190 mit Hinweisen). Unter Berücksichtigung aller entscheidenden Umstände kann schon eine einzige Verurteilung wegen einer besonders schwer wiegenden Straftat zur Ausweisung führen. Dem Gesichtspunkt der Rückfallgefahr kommt ausserhalb des Geltungsbereichs des Freizügigkeitsabkommens nicht vorrangige Bedeutung zu und es muss im Zusammenhang mit Gewaltdelikten selbst ein relativ geringes Restrisiko nicht hingenommen werden (zum Ganzen: <ref-ruling> E. 4.2 bis 4.4 S. 185 ff. mit Hinweisen).
3. 3.1 Der Beschwerdeführer wurde zu einer Zuchthausstrafe von 5 1⁄2 Jahren verurteilt. Damit liegt ein Ausweisungsgrund nach Art. 10 Abs. 1 lit. a ANAG vor. Zu prüfen bleibt, ob die Nichtverlängerung der Aufenthaltsbewilligung verhältnismässig ist.
3.2 Der Beschwerdeführer macht vorab geltend, es sei unzulässig, im Strafregister gelöschte Vorstrafen ausländerrechtlich zu berücksichtigen.
3.2.1 Zutreffend ist, dass nach <ref-law>, in der seit 1. Januar 2007 in Kraft stehenden Fassung, aus dem Strafregister entfernte Urteile dem Betroffenen nicht mehr entgegengehalten werden dürfen. An diese Urteile dürfen somit generell keine Rechtsfolgen mehr geknüpft werden (vgl. <ref-ruling> E. 2.10 mit Hinweisen; zur Publikation bestimmtes Urteil 6B_538/2008 vom 7. Januar 2009 E. 2.4-2.5). Dieses Verwertungsverbot von gelöschten Strafen gilt nicht nur für die Strafverfolgungsbehörden, sondern für sämtliche Behörden, die Strafregisterdaten aus VOSTRA beziehen (PATRICK GRUBER, Basler Kommentar, N 8/9 zu <ref-law>), somit auch für das Bundesamt für Migration (<ref-law>) und für die kantonalen Fremdenpolizeibehörden (<ref-law>). Aus den Materialien (BBl 1999 II 2168) ergibt sich allerdings, dass der Gesetzgeber nur strafrechtlich überlegt hat. Wohl wird (allgemein) ausgeführt, es lasse sich nicht rechtfertigen, einem Straftäter noch nach Jahrzehnten nach Verbüssung der Strafe eine Straftat von Staates wegen vorzuhalten. Aus dem Textzusammenhang und der Bezugnahme auf die Strafverbüssung ergibt sich hingegen, dass einzig strafrechtliche Zusammenhänge angesprochen sind. Im Bereich des Ausländerrechts kann <ref-law> nur zur Folge haben, dass die Bewilligungsverweigerung, der Widerruf einer ausländerrechtlichen Bewilligung, deren Nichtverlängerung sowie die altrechtliche Ausweisung nicht gestützt auf eine gelöschte Straftat verfügt werden können, was logischerweise ohnehin nicht in Betracht fällt. Es muss somit ein genügend gewichtiger aktueller Anlass vorliegen, um eine entsprechende fremdenpolizeiliche Massnahme zu rechtfertigen.
3.2.2 Bei der im Rahmen der Verhältnismässigkeitsprüfung vorzunehmenden ausländerrechtlichen Interessenabwägung kann indessen nicht ausgeblendet werden, wie sich der betroffene Ausländer während seiner gesamten Anwesenheit in der Schweiz verhalten hat. Eine lange Aufenthaltsdauer fällt grundsätzlich zu Gunsten eines weiteren Verbleibs ins Gewicht, sofern sich der Ausländer während dieser Zeit klaglos verhalten hat. Müssten für die ausländerrechtliche Würdigung der Anwesenheitsdauer inzwischen gelöschte Strafen, die den Fremdenpolizeibehörden bekannt sind, sowie allenfalls eine gestützt darauf schon früher verfügte fremdenpolizeiliche Verwarnung oder eine Einreisesperre ausser Acht gelassen werden, käme es zu einer verzerrten Beurteilung. Es wäre widersprüchlich, gestützt auf das absolute Verwertungsverbot davon auszugehen, dass sich ein Ausländer während Jahren hier wohl verhalten hat und dies gar noch zu seinen Gunsten zu berücksichtigen, nur weil die während dieser Zeitspanne erwirkten Sanktionen im Strafregister gelöscht worden sind und obwohl der Betroffene in Wirklichkeit damals Anlass zu Klagen gegeben hat. Für die ausländerrechtliche Interessenabwägung ist demnach das Verwertungsverbot gemäss <ref-law> insofern zu relativieren, als es den Fremdenpolizeibehörden nicht verwehrt ist, strafrechtlich relevante Daten, die sich in ihren Akten befinden oder ihnen anderweitig bekannt sind bzw. werden, namentlich solche, die Anlass zu einer fremdenpolizeilichen Verwarnung gaben, nach deren Löschung im Strafregister in die Beurteilung des Verhaltens des Ausländers während seiner gesamten Anwesenheit in der Schweiz einzubeziehen, wobei selbstverständlich weit zurückliegenden Straftaten in der Regel keine grosse Bedeutung mehr zukommen kann, insbesondere wenn es sich wie hier um relativ geringfügige Verfehlungen handelt.
3.2.2 Bei der im Rahmen der Verhältnismässigkeitsprüfung vorzunehmenden ausländerrechtlichen Interessenabwägung kann indessen nicht ausgeblendet werden, wie sich der betroffene Ausländer während seiner gesamten Anwesenheit in der Schweiz verhalten hat. Eine lange Aufenthaltsdauer fällt grundsätzlich zu Gunsten eines weiteren Verbleibs ins Gewicht, sofern sich der Ausländer während dieser Zeit klaglos verhalten hat. Müssten für die ausländerrechtliche Würdigung der Anwesenheitsdauer inzwischen gelöschte Strafen, die den Fremdenpolizeibehörden bekannt sind, sowie allenfalls eine gestützt darauf schon früher verfügte fremdenpolizeiliche Verwarnung oder eine Einreisesperre ausser Acht gelassen werden, käme es zu einer verzerrten Beurteilung. Es wäre widersprüchlich, gestützt auf das absolute Verwertungsverbot davon auszugehen, dass sich ein Ausländer während Jahren hier wohl verhalten hat und dies gar noch zu seinen Gunsten zu berücksichtigen, nur weil die während dieser Zeitspanne erwirkten Sanktionen im Strafregister gelöscht worden sind und obwohl der Betroffene in Wirklichkeit damals Anlass zu Klagen gegeben hat. Für die ausländerrechtliche Interessenabwägung ist demnach das Verwertungsverbot gemäss <ref-law> insofern zu relativieren, als es den Fremdenpolizeibehörden nicht verwehrt ist, strafrechtlich relevante Daten, die sich in ihren Akten befinden oder ihnen anderweitig bekannt sind bzw. werden, namentlich solche, die Anlass zu einer fremdenpolizeilichen Verwarnung gaben, nach deren Löschung im Strafregister in die Beurteilung des Verhaltens des Ausländers während seiner gesamten Anwesenheit in der Schweiz einzubeziehen, wobei selbstverständlich weit zurückliegenden Straftaten in der Regel keine grosse Bedeutung mehr zukommen kann, insbesondere wenn es sich wie hier um relativ geringfügige Verfehlungen handelt.
3.3 3.3.1 Ausgangspunkt und Massstab für die fremdenpolizeiliche Interessenabwägung ist - wie erwähnt - die vom Strafrichter verhängte Freiheitsstrafe, d.h. das strafrechtliche Verschulden.
Der Beschwerdeführer hat ein schweres Gewaltdelikt begangen: Im Verlauf einer handgreiflichen Auseinandersetzung unter Staatsangehörigen des ehemaligen Jugoslawien schoss der Beschwerdeführer einem Widersacher, der die Flucht ergriff, aus kurzer Distanz mit einer Faustfeuerwaffe nach und verletzte ihn mit einem Streifschuss im Lendenbereich. Er wurde deshalb unter anderem der versuchten vorsätzlichen Tötung schuldig gesprochen. Die Vorinstanz ist gestützt auf das Urteil des Kantonsgerichts St. Gallen vom 30. Juni 2004 zu Recht von einem schweren Verschulden des Beschwerdeführers ausgegangen. Im ausländerrechtlichen Verfahren besteht regelmässig kein Raum, die Beurteilung des Strafrichters in Bezug auf das Verschulden zu relativieren (Urteile 2C_488/2007 vom 6. Februar 2008 E. 3.1; 2A.16/2007 vom 10. Mai 2007 E. 3.1.1; 2A.373/2006 vom 15. September 2006 E. 3.1). Im Übrigen hat das Kantonsgericht bei der Festsetzung des Strafmasses von 5 1⁄2 Jahren Zuchthaus der langen Verfahrensdauer Rechnung getragen.
Aufgrund der hohen Gewaltbereitschaft, die er beim versuchten Tötungsdelikt erkennen liess, vermögen seine Beteuerungen betreffend sein zukünftiges Wohlverhalten diesbezügliche Bedenken nicht auszuräumen. Im Übrigen beging er noch während des Strafvollzugs eine massive Geschwindigkeitsüberschreitung auf der Autobahn, was nicht auf eine grundlegende Haltungsänderung bezüglich der hier geltenden gesetzlichen Ordnung hindeutet. Dass der Beschwerdeführer seit der bedingten Entlassung im April 2008 bzw. während des hängigen fremdenpolizeilichen Verfahrens nicht mehr straffällig geworden ist, steht dieser Würdigung nicht entgegen. Wie die Vorinstanz zu Recht ausführt, erscheint ein psychiatrisches Gutachten zum Vornherein nicht als geeignet, für das vorliegende Verfahren entscheidende neue Erkenntnisse betreffend Rückfallgefahr zu liefern. Aus dem Umstand, dass die Landesverweisung bedingt ausgesprochen wurde, kann der Beschwerdeführer sodann nichts zu seinen Gunsten ableiten, zumal dies die verfügte ausländerrechtliche Massnahme nicht ausschliesst (<ref-ruling> E. 3.2 und 7.4 S. 216 f. und 222 f.). Soweit es hier aufgrund der Schwere der Straftat und des damit verbundenen Verschuldens überhaupt noch auf eine Rückfallgefahr ankommt, kann jedenfalls selbst ein geringes Risiko nicht hingenommen werden. Zusammenfassend ergibt sich, dass ein gewichtiges öffentliches Interesse an der Entfernung des Beschwerdeführers aus der Schweiz besteht.
3.3.2 Der Beschwerdeführer hält sich zwar seit 26 Jahren in der Schweiz auf. Zu berücksichtigen ist jedoch, dass er erst im Alter von 30 Jahren einreiste. Er ist somit in seinem Heimatland aufgewachsen und hat dort auch die prägenden Jugendjahre verbracht. Die verhältnismässig lange Aufenthaltsdauer wird zudem durch die Umstände seiner Anwesenheit relativiert: Aufgrund des bereits ein Jahr nach seiner Einreise verfügten Widerrufs der Aufenthaltsbewilligung und der in der Folge wegen seines Verhaltens dreimal verweigerten Erteilung der Niederlassungsbewilligung konnte der Beschwerdeführer nicht davon ausgehen, dass sein Verbleiben in der Schweiz ohne weiteres auf Dauer gewährleistet war, zumal er über keinen Anspruch auf Aufenthaltsbewilligung verfügte. Umso mehr musste er nach seiner schwersten Straftat im Dezember 1998 damit rechnen, die Schweiz verlassen zu müssen. Vorerst konnte er wegen des hängigen Strafverfahrens und ab November 2004, weil er sich im Strafvollzug (bis April 2008) befand, in der Schweiz verbleiben.
Trotz relativ langem Aufenthalt ist weder beruflich noch gesellschaftlich eine gute Integration in der Schweiz ersichtlich, auch wenn der Beschwerdeführer seine hohe Verschuldung inzwischen offenbar abgebaut hat und keine Betreibungen mehr aufweist. Den Akten ist zu entnehmen, dass er mehrheitlich zu Leuten aus dem ehemaligen Jugoslawien Kontakt pflegt und trotz langjährigem Aufenthalt die deutsche Sprache nicht beherrscht. Obwohl der Beschwerdeführer schon lange in der Schweiz lebt, kann unter diesen Umständen nicht von einer eigentlichen Verwurzelung gesprochen werden. Nach den verbindlichen Feststellungen der Vorinstanz spricht der Beschwerdeführer die heimatliche Sprache und ist mit den sozialen und kulturellen Gepflogenheiten in Bosnien und Herzegowina nach wie vor vertraut, weshalb er sich dort wieder wird zurecht finden können. Die Rückkehr in sein Heimatland, wo sich die Verhältnisse seit seinem Weggang nachhaltig verändert haben, mag ihn hart treffen, ist aber grundsätzlich zumutbar. Die geltend gemachten gesundheitlichen Probleme stehen einer Ausreise nicht entgegen, selbst wenn die medizinische Versorgung in den ländlichen Gebieten von Bosnien und Herzegowina nicht dem schweizerischen Standard entsprechen sollte. Die Notwendigkeit für einen Verbleib in der Schweiz aufgrund des gesundheitlichen Zustands des Beschwerdeführers ist jedenfalls nicht ausgewiesen. Gemäss Arztzeugnis steht der Beschwerdeführer in lockerer medizinischer Kontrolle. Dass die Medikamente, die er regelmässig einnehmen muss, im Heimatland nicht erhältlich wären, wird nicht dargetan. Im Übrigen könnten ihm auch seine beiden in der Schweiz wohnhaften Söhne nötigenfalls beim Besorgen der Medikamente behilflich sein.
3.3.3 Die vom Beschwerdeführer im März 2006 während des Strafvollzugs eingegangene Ehe ist für die vorliegende Interessenabwägung bloss von untergeordneter Bedeutung. Im Zeitpunkt der Heirat hatte die Ehegattin von der Straffälligkeit und, da sie den Beschwerdeführer bereits seit längerem kannte, von seinem Vorleben bestens Kenntnis und musste folglich damit rechnen, die Ehe mit ihm nicht in der Schweiz leben zu können. Ob es der hier eingebürgerten Ehefrau, die ursprünglich ebenfalls aus Bosnien und Herzegowina stammt, zumutbar wäre, dem Beschwerdeführer ins Heimatland zu folgen, kann unter diesen Umständen dahingestellt bleiben. Falls die Ehefrau sich entscheiden sollte, in der Schweiz zu verbleiben, ist es dem Beschwerdeführer zudem nicht verwehrt, sie hier zu besuchen, da bloss eine Bewilligungsverweigerung und keine Ausweisung verfügt wurde.
3.3.4 Die beiden Söhne aus erster Ehe sind volljährig. Der Beschwerdeführer macht jedoch geltend, der jüngere Sohn befinde sich noch in der Ausbildung und wohne bei ihm. Selbst wenn die Ehefrau des Beschwerdeführers den zwanzigjährigen Stiefsohn noch finanziell unterstützt, besteht zwischen diesem und dem Beschwerdeführer jedenfalls nicht ein eigentliches Abhängigkeitsverhältnis, das ausserhalb der Kernfamilie einen Anspruch auf Aufenthalt gestützt auf den Familienschutz nach Art. 8 EMRK entstehen lassen könnte. Abgesehen davon, dass der Sohn erwachsen ist, leben zudem auch seine leibliche Mutter sowie sein älterer Bruder in der Schweiz, weshalb er auch nach Ausreise des Vaters und allenfalls der Stiefmutter ohnehin nicht auf sich allein gestellt wäre.
3.3.5 Aufgrund des Gesagten überwiegt das öffentliche Interesse an der Entfernung des Beschwerdeführers aus der Schweiz dessen privates Interesse an einem weiteren Verbleib.
3.4 Wenn das Verwaltungsgericht bei dieser Sachlage die Voraussetzungen für eine Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers als erfüllt erachtete, verstiess es damit weder gegen Bundesrecht noch gegen staatsvertragliche Verpflichtungen.
4. 4.1 Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
4.2 Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (<ref-law>).

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 Kantonalen Ausländeramt St. Gallen, dem Sicherheits- und Justizdepartement sowie dem Verwaltungsgericht des Kantons St. Gallen und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 24. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs