Sachverhalt:
A. Der serbische Staatsangehörige Y._ (geb. 10. Oktober 1963) kam 1970 erstmals in die Schweiz. In der Folge war er in Zürich angemeldet, lebte allerdings während mehreren Jahren im damaligen Jugoslawien bei seinen Grosseltern und verbrachte nur die Ferien bei seinen Eltern in der Schweiz. Erst 1980 reiste er definitiv ein und erhielt eine Niederlassungsbewilligung.
Am 25. Juni 1987 wurde er vom Obergericht des Kantons Zürich wegen bandenmässigen Raubs, Versuchs dazu, Raubs sowie Raubversuchs zu dreissig Monaten Zuchthaus und zu zehn Jahren Landesverweis verurteilt. Wegen fortgesetzten Raubs und Versuchs dazu fällte das Obergericht des Kantons Zürich mit Urteil vom 11. Januar 1989 eine Zusatzstrafe von zehn Monaten Gefängnis unbedingt. Im Jahre 1991 wurde er unter dem Namen Y._ aus der Schweiz ausgeschafft.
B. Ungefähr ab 1992 führte er den neuen Namen Y.A._. Im gleichen Jahr heiratete er die in der Schweiz niedergelassene Landsfrau Z.B._ und nahm in der Folge deren Namen an. Am 7. Februar 1993 reiste er unter dem Namen Y.B._ wieder in die Schweiz ein, wo ihm gestützt auf die Heirat im Kanton Solothurn eine Aufenthaltsbewilligung erteilt wurde. 1994 zogen die Ehegatten mit der inzwischen geborenen Tochter nach Zürich, wo in der Folge ein zweites Kind geboren wurde. Mit Urteil des Obergerichts des Kantons Zürich vom 2. Dezember 1999 wurde die Ehe von Z.B._ und Y.B._ geschieden.
Am 11. Dezember 1996 wurde Y.B._ verhaftet. Im Rahmen der polizeilichen Abklärungen stellte sich heraus, dass Y.B._ und Y._ dieselbe Person sind und dass der Betroffene unter dem Namen Y._ bereits für die Dauer von zehn Jahren des Landes verwiesen worden war. Mit Urteil vom 11. März 1999 wurde Y.B._ vom Geschworenengericht des Kantons Zürich der mehrfach versuchten vorsätzlichen Tötung, des Verweisungsbruchs sowie des verbotenen Waffentragens schuldig gesprochen und zu elf Jahren Zuchthaus sowie lebenslänglichem Landesverweis verurteilt. Nachdem dieses Urteil auf kantonale Nichtigkeitsbeschwerde hin aufgehoben worden war, bestrafte ihn das Geschworenengericht mit Urteil vom 4. Juli 2001 mit zehn Jahren Zuchthaus und lebenslänglichem Landesverweis.
Y.B._ wurde am 27. Oktober 2005 nach Belgrad ausgeschafft. Bereits am 12. Oktober 2005 verfügte das Bundesamt für Migration eine Einreisesperre auf unbestimmte Dauer.
C. Im Januar 2007 heiratete Y._ (alias Y.B._) in Belgrad die Schweizer Bürgerin X._, die er während des Strafvollzuges kennengelernt hatte. Am 19. März 2008 stellte X._ ein Familiennachzugsgesuch für ihren Ehemann. Die Abteilung für Ausländerfragen des Departements des Innern des Kantons Solothurn wies das Gesuch mit Verfügung vom 15. April 2009 ab. Dagegen beschwerte sich X._ ohne Erfolg beim Verwaltungsgericht des Kantons Solothurn.
D. Mit Eingaben vom 18. Juli 2009 bzw. vom 19. Juli 2009 haben X._ und Y._ "Rekurs" an das Bundesgericht erhoben mit dem sinngemässen Antrag, das Urteil des Verwaltungsgerichts des Kantons Solothurn aufzuheben und den Familiennachzug zu gewähren.
Das Bundesgericht hat die kantonalen Akten beigezogen, aber keine Vernehmlassungen eingeholt.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Gemäss Art. 42 Abs. 1 des auf den 1. Januar 2008 in Kraft getretenen, hier anwendbaren Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) haben ausländische Ehegatten von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen.
Als Schweizer Bürgerin steht der Beschwerdeführerin gestützt auf die erwähnte Gesetzesbestimmung im Grundsatz ein Anspruch auf Nachzug ihres Ehegatten zu, mit welchem gerade bezweckt wird, die rechtlichen Voraussetzungen für ein eheliches Zusammenleben in der Schweiz zu schaffen. Ein identischer Anspruch ergibt sich auch aus Art. 8 Ziff. 1 EMRK und <ref-law>, da die ehelichen Beziehungen zwischen den Ehegatten - soweit ersichtlich - intakt sind und den Umständen entsprechend gelebt werden (vgl. <ref-ruling> E. 5.3.1 S. 211 mit Hinweisen). Ob der Anspruch erloschen ist, weil ein Widerrufsgrund nach Art. 63 AuG (in Verbindung mit Art. 51 Abs. 1 lit. b AuG) vorliegt, ist eine Frage der materiellen Beurteilung und nicht der Zulässigkeit des Rechtsmittels (<ref-ruling> E. 1.1.5 S. 149 f.). Auf die Beschwerde ist somit einzutreten.
Der ausländische Ehegatte (Beschwerdeführer 2) hatte zwar im kantonalen Beschwerdeverfahren ebenfalls eine Eingabe gegen die Verweigerung des Familiennachzugs eingereicht. Indessen ist allein die Ehegattin (Beschwerdeführerin 1) Adressatin des angefochtenen Urteils. Ob der Beschwerdeführer 2 unter diesen Umständen zur Beschwerde an das Bundesgericht berechtigt ist (vgl. <ref-law>), kann jedoch dahin gestellt bleiben, da auf die Beschwerde der Beschwerdeführerin 1 jedenfalls einzutreten ist und das Rechtsmittel ohnehin nicht durchdringt.
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). 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 <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
Die (nicht belegten) im Widerspruch mit dem im Januar erstellten Arbeitsvertrag stehenden tatsächlichen Behauptungen der Beschwerdeführerin, sie arbeite zu mehr als 12% und beziehe seit vier Monaten keine Sozialhilfe mehr, sind neu und können daher im vorliegenden Verfahren nicht gehört werden. Im Übrigen vermöchten diese Vorbringen am Ausgang des Verfahrens ohnehin nichts zu ändern. Inwieweit die von den Beschwerdeführern eingereichten Beilagen berücksichtigt werden könnten, kann offen bleiben, da nicht ersichtlich ist, in welchem Zusammenhang sie mit dem Gegenstand des vorliegenden Verfahrens stehen bzw. was damit belegt werden sollte.
2. 2.1 Nach Art. 42 Abs. 1 AuG hat der ausländische Ehegatte eines Schweizer Bürgers Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn er mit diesem zusammenwohnt, der Bewilligungsanspruch nicht rechtsmissbräuchlich geltend gemacht wird und kein Widerrufsgrund nach Art. 63 AuG vorliegt. Ein solcher besteht unter anderem, wenn die ausländische Person "zu einer längerfristigen Freiheitsstrafe" verurteilt worden ist (Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. b AuG) oder sie "in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat oder diese gefährdet oder die innere oder äussere Sicherheit gefährdet" (Art. 63 Abs. 1 lit. b AuG) sowie wenn die Ausländerin oder der Ausländer oder eine Person, für die sie oder er zu sorgen hat, "dauerhaft und in erheblichem Mass auf Sozialhilfe angewiesen ist" (Art. 63 Abs. 1 lit. c AuG).
2.2 Die Anwendung der einzelnen Widerrufsgründe kann weitgehend in Anlehnung an die bisherige Praxis zum ANAG erfolgen (vgl. BBl 2002 3810; Rahel Martin-Küttel, Aufenthaltsbeendigung nach altem und neuem Recht, in: Achermann et al., Jahrbuch für Migrationsrecht 2006/2007, S. 3 ff., dort S. 9, 22 f. und 29; Zünd/Arquint, Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Uebersax et al., Ausländerrecht, 2. Aufl., Basel 2009, Rz. 8.55 und 8.28). Der Widerruf bzw. die Verweigerung der Bewilligung rechtfertigt sich auch nach dem neuen Recht nur, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung die entsprechende Massnahme als verhältnismässig erscheinen lässt (vgl. <ref-ruling> E. 2a S. 523; Rahel Martin-Küttel, a.a.O., S. 8 f.; Marc Spescha, in: Spescha/Thür/Zünd/Bolzli, Migrationsrecht, Zürich 2008, Rz. 4 zu Art. 51 AuG; Zünd/Arquint, a.a.O., Rz. 8.55). Dabei sind namentlich die Schwere des Verschuldens, die Dauer der bisherigen Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. Art. 96 AuG; altrechtlich Art. 11 Abs. 3 ANAG und Art. 16 Abs. 3 ANAV; <ref-ruling> E. 3 und 4 S. 216 ff.).
2.3 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.). Ein solcher ist statthaft, falls 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.
3. 3.1 Der Beschwerdeführer ist zu einer Zuchthausstrafe von 10 Jahren und zu lebenslänglicher Landesverweisung verurteilt worden. Er erfüllt damit den Widerrufsgrund nach Art. 63 Abs. 1 lit. a in Verbindung mit Art. 62 lit. b AuG.
Das Verwaltungsgericht erachtet zusätzlich den Widerrufsgrund gemäss Art. 63 Abs. 1 lit. b AuG als erfüllt. Eine Gefährdung der öffentlichen Sicherheit und Ordnung besteht, wenn konkrete Anhaltspunkte dafür sprechen, dass der Aufenthalt der betroffenen Person in der Schweiz mit erheblicher Wahrscheinlichkeit zu einem Verstoss gegen die öffentliche Sicherheit und Ordnung führt (<ref-law> [SR 142.201]). Aufgrund des bisherigen Verhaltens und der mangelnden Einsicht des Beschwerdeführers bezüglich seiner Schuld im Zusammenhang mit der begangenen Straftat ist der Schluss der Vorinstanz nicht zu beanstanden.
Die Annahme der Vorinstanz, dass auch der Widerrufsgrund nach Art. 63 Abs. 1 lit. c AuG (dauerhafte und erhebliche Beanspruchung der Sozialhilfe) gegeben ist, erweist sich gestützt auf die für das Bundesgericht verbindlichen Feststellungen (vgl. E. 1.3) ebenfalls als vertretbar. Danach geht die Beschwerdeführerin einer Erwerbstätigkeit mit einem Beschäftigungsgrad von bloss 12% nach und bezieht daneben Sozialhilfe. Schon aufgrund seines gesundheitlichen Zustandes erscheint wenig wahrscheinlich, dass der Ehemann eine Erwerbstätigkeit aufnehmen und ein genügendes Einkommen erzielen könnte. Im Übrigen schuldet er dem Obergericht des Kantons Zürich Gerichtskosten in der Höhe von rund Fr. 80'000.--. Weitere Ausführungen dazu erübrigen sich indessen, da bereits ein einziger Widerrufsgrund genügt, um den Anwesenheitsanspruch des Beschwerdeführers zum Erlöschen zu bringen.
Zu prüfen ist, ob sich die Verweigerung des Familiennachzugs als verhältnismässig erweist.
3.2 Der Beschwerdeführer hat ein schweres Gewaltdelikt begangen und wurde deshalb unter anderem der versuchten vorsätzlichen Tötung schuldig gesprochen und zu einer Zuchthausstrafe von zehn Jahren verurteilt. In den Beschwerdeeingaben an das Bundesgericht beschränken sich die Beschwerdeführer im Wesentlichen darauf, die begangene Straftat als weniger gravierend erscheinen zu lassen bzw. die Schuld anderen Personen zuzuweisen. Im ausländerrechtlichen Verfahren besteht aber regelmässig kein Raum, die Beurteilung des Strafrichters in Bezug auf das Verschulden zu relativieren (Urteil 2C_477/2008 vom 24. Februar 2009 E. 3.3.1 mit Hinweisen). Die Vorinstanz ist gestützt auf das Urteil des Geschworenengerichts des Kantons Zürich zu Recht von einem schweren Verschulden ausgegangen. Der Umstand, dass der Beschwerdeführer bereits wiederholt Straffälligkeit geworden ist und seine Schuld auch heute nicht einsieht, lässt zudem ein Rückfallrisiko nicht ausschliessen. Das öffentliche Interesse, den Beschwerdeführer von der Schweiz fernzuhalten ist somit gewichtig.
3.2 Der Beschwerdeführer hat ein schweres Gewaltdelikt begangen und wurde deshalb unter anderem der versuchten vorsätzlichen Tötung schuldig gesprochen und zu einer Zuchthausstrafe von zehn Jahren verurteilt. In den Beschwerdeeingaben an das Bundesgericht beschränken sich die Beschwerdeführer im Wesentlichen darauf, die begangene Straftat als weniger gravierend erscheinen zu lassen bzw. die Schuld anderen Personen zuzuweisen. Im ausländerrechtlichen Verfahren besteht aber regelmässig kein Raum, die Beurteilung des Strafrichters in Bezug auf das Verschulden zu relativieren (Urteil 2C_477/2008 vom 24. Februar 2009 E. 3.3.1 mit Hinweisen). Die Vorinstanz ist gestützt auf das Urteil des Geschworenengerichts des Kantons Zürich zu Recht von einem schweren Verschulden ausgegangen. Der Umstand, dass der Beschwerdeführer bereits wiederholt Straffälligkeit geworden ist und seine Schuld auch heute nicht einsieht, lässt zudem ein Rückfallrisiko nicht ausschliessen. Das öffentliche Interesse, den Beschwerdeführer von der Schweiz fernzuhalten ist somit gewichtig.
3.3 3.3.1 Der Beschwerdeführer ist 1980 als Siebzehnjähriger im Rahmen des Familiennachzugs in die Schweiz gekommen. Er ist somit in seinem Heimatland aufgewachsen. In der Schweiz hat er sich weder beruflich noch gesellschaftlich integriert. 1991 wurde er im Alter von 28 Jahren aufgrund seiner Straffälligkeit aus der Schweiz ausgeschafft. Mittels Namensänderung und Heirat einer hier niederlassungsberechtigten Landsfrau gelang es ihm trotz Landesverweis für die Dauer von zehn Jahren, im Februar 1993 erneut in die Schweiz einzureisen. Er wurde jedoch wie erwähnt wiederum schwer straffällig. Bei seiner bedingten Entlassung erklärte er sich bereit, in sein Heimatland zurückzukehren, wobei er damals bereits eine Beziehung mit der Beschwerdeführerin hatte. Am 27. Oktober 2005 wurde er nach Serbien ausgeschafft. Es ist davon auszugehen, dass der Beschwerdeführer, der mit der heimatlichen Sprache und Kultur bestens vertraut ist, seither in Serbien wieder ein soziales Netz und eine neue Existenz aufgebaut hat.
Die geltend gemachten gesundheitlichen Probleme (HIV-Infektion) stehen der Verweigerung des Familiennachzugs nicht entgegen, selbst wenn die medizinische Versorgung in Serbien nicht dem schweizerischen Standard entsprechen sollte. Der Beschwerdeführer wohnt zudem in Belgrad, wo öffentliche sowie private Kliniken bestehen und die medizinische Versorgung besser gewährleistet ist als in den ländlichen Gebieten. Dass Medikamente, die er regelmässig einnehmen muss, im Heimatland nicht erhältlich wären, wird nicht dargetan.
3.3.2 Die nach der (zweiten) Ausschaffung des Beschwerdeführers im Heimatland eingegangene Ehe mit der Beschwerdeführerin ist für die vorliegende Interessenabwägung bloss von untergeordneter Bedeutung. Die Beschwerdeführerin hat ihren Ehegatten durch ein Inserat kennen gelernt, als er sich im Strafvollzug befand, und hatte daher Kenntnis von seiner Verurteilung. Im Zeitpunkt der Heirat mussten die Eheleute folglich damit rechnen, die Ehe nicht in der Schweiz leben zu können, dies umso mehr als der Ehemann damals bereits in sein Heimatland ausgeschafft worden war.
3.3.3 Die Beschwerdeführerin wendet ein, es sei ihr nicht zuzumuten, im Heimatland des Ehemannes zu leben. Dazu ist zu bemerken, dass bei einem mit einem Schweizer Bürger verheirateten Ausländer, der erstmals oder nach bloss kurzer Aufenthaltsdauer um die Erneuerung seiner Bewilligung ersucht, das Bundesgericht bisher annahm, dass die Grenze, von der an in der Regel selbst dann keine solche mehr erteilt wird, wenn dem Ehepartner die Ausreise un- oder nur schwer zumutbar erscheint, bei einer Freiheitsstrafe von zwei Jahren liegt. In dieser Situation bedurfte es praxisgemäss aussergewöhnlicher Umstände, um die Erteilung einer Aufenthaltsbewilligung dennoch zu rechtfertigen ("Reneja"-Praxis: <ref-ruling> ff.), auch wenn es sich bei der Zweijahresregel um keine feste Grenze handelt, die im Einzelfall nicht über- oder unterschritten werden dürfte. An dieser Praxis ist auch unter der Herrschaft des neuen Ausländergesetzes festzuhalten (zur Publikation bestimmtes Urteil 2C_295/2009 vom 25. September 2009, E. 4.4).
Es trifft zwar zu, dass sich der Beschwerdeführer bereits mehrere Jahre in der Schweiz aufgehalten hat, allerdings wird die Dauer seines Aufenthalts durch die Umstände seines Verbleibs relativiert. Abgesehen davon, dass es ihm nach seiner ersten Ausschaffung ohne Namensänderung kaum gelungen wäre, wiederum ein Anwesenheitsrecht zu erwirken, hat er seinen zweiten Aufenthalt in der Schweiz zu einem grossen Teil in Haft bzw. im Strafvollzug verbracht. Zudem wurde er zu einer Freiheitsstrafe verurteilt, die weit über dem erwähnten Richtwert von zwei Jahren liegt. Ob der Beschwerdeführerin, die immerhin mehrmals in Serbien zu Besuch war und bereits einige Zeit bei ihrem Ehemann gelebt hat, zumutbar ist, diesem dorthin zu folgen, kann bei dieser Sachlage dahingestellt bleiben.
3.3.4 Aus der Beziehung zu seinen beiden Kindern aus erster Ehe, die unter der elterlichen Sorge der Mutter leben, kann der Beschwerdeführer nichts zu seinen Gunsten ableiten. In der Regel kann sich im Hinblick auf eine Bewilligungserteilung nur derjenige auf Art. 8 EMRK berufen, der mit der in der Schweiz anwesenheitsberechtigten Person zusammen lebt. Ein Besuchsrecht gegenüber einem in der Schweiz anwesenheitsberechtigten Kind verschafft dem ausländischen Elternteil daher im Allgemeinen noch keinen Anspruch auf dauernde Anwesenheit. Die Aufenthaltsbewilligung ist nach bundesgerichtlicher Rechtsprechung nur dann zu erteilen oder zu erneuern, wenn in wirtschaftlicher und affektiver Hinsicht eine besonders enge Beziehung zum Kind besteht, diese wegen der Distanz zum Heimatland des Ausländers praktisch nicht mehr aufrechterhalten werden könnte und das bisherige Verhalten des Betroffenen in der Schweiz zu keinerlei Klagen Anlass gegeben hat (<ref-ruling> E. 3c S. 5, 22 E. 4; Urteil 2C_870/2008 vom 26. Mai 2009 E. 2.2). Ob der Beschwerdeführer zu den Kindern eine den erwähnten Anforderungen entsprechende besonders enge Beziehung pflegt, ist weder dargetan noch ersichtlich, kann jedoch dahingestellt bleiben, da nicht nur ein tadelloses Verhalten des Beschwerdeführers fehlt, sondern aufgrund seiner massiven Straffälligkeit vielmehr sogar die Voraussetzungen für einen Eingriff in das Recht auf Achtung des Familienlebens gemäss Art. 8 Ziff. 2 EMRK erfüllt sind (<ref-ruling> E. 4.1 S. 22 f.).
3.4 Zusammenfassend ergibt sich, dass das Verwaltungsgericht demnach zu Recht das öffentliche Interesse an der Fernhaltung des Beschwerdeführers höher gewichtet hat als dessen private Interessen an der Anwesenheit in der Schweiz.
4. 4.1 Aufgrund des Gesagten erweist sich die Beschwerde als unbegründet und ist abzuweisen, soweit darauf einzutreten ist.
4.2 Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig (Art. 65 in Verbindung mit Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Departement des Innern und dem Verwaltungsgericht des Kantons Solothurn sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 4. November 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Müller Dubs