Faits:
A. A.a Le 17 mai 2007, A._, médecin-conseil auprès de l'assurance invalidité, a reçu des menaces de mort par téléphone. Il a ensuite réceptionné trois lettres de menaces, les 13 juin, 27 juin et 29 octobre 2007. Ces courriers faisaient référence à la suppression d'une rente AI et, pour certains, comportaient une photocopie d'un pistolet de marque Walther.
A raison de ces faits, A._ et sa fille, B._, également menacée dans les courriers précités, ont déposé plainte contre inconnu.
A.b Plusieurs éléments ont conduit les autorités à arrêter X._ en date du 25 novembre 2007. D'une part, ce dernier était titulaire d'une arme à feu de marque Walther. D'autre part, il était très défavorablement connu des services de police, notamment pour infractions contre le patrimoine, menaces, diffamation, voies de fait, détention illégale d'armes. De plus, il était au bénéfice, tout comme ses enfants, d'une rente d'invalidité et l'assurance l'avait informé, en juillet 2007, que la rente de son fils, C._, allait être supprimée. Enfin, il a admis, lors d'un interrogatoire, avoir écrit une des trois lettres de menaces et son fils l'a également mis en cause.
Par ordonnance du 5 décembre 2007, X._ a été remis en liberté, au motif que l'arme retrouvée chez lui n'était pas avec certitude celle dont la photocopie figurait sur certaines lettres de menaces, que ses dénégations étaient constantes depuis son inculpation, que ses aveux à la police n'avaient jamais été complets et que les charges à son encontre, sans avoir disparu, avaient diminué au point de ne plus justifier son maintien en détention.
A.c Le 5 décembre 2007, B._ a reçu trois nouvelles lettres de menace. L'une d'elles a été agrafée avec un article de presse relatant l'arrestation de X._, l'expéditeur demandant au destinataire de laisser ce malheureux.
B. Par décision du 22 août 2008, le Procureur général du canton de Genève a classé la procédure dirigée contre X._, en raison d'une prévention pénale insuffisante.
Par ordonnance du 19 novembre 2008, la Chambre d'accusation genevoise a rejeté le recours de X._, estimant qu'un non-lieu ne pouvait être prononcé à la place du classement, le dossier comportant trop d'indices à charge.
C. Invoquant l'arbitraire dans l'application du droit cantonal et l'appréciation des preuves ainsi qu'une violation de la présomption d'innocence, X._ dépose un recours en matière pénale contre l'ordonnance précitée dont il demande l'annulation. Il requiert également l'assistance judiciaire.

Considérant en droit:
1. En procédure pénale genevoise, le non-lieu ne se conçoit qu'à l'issue d'une instruction suffisamment complète pour que l'autorité compétente puisse acquérir la conviction que les charges font défaut ou qu'un motif de droit conduirait, en juridiction de jugement, à reconnaître l'action pénale comme mal fondée (ATF 6B_793/2007 consid. 2).
Le bénéficiaire d'un classement en opportunité ne peut demander le non-lieu tant que des indices sérieux de culpabilité subsistent. Etant donné qu'il ne s'agit pas d'un jugement sur le fond, il n'est pas nécessaire que la preuve des faits coupables soit rapportée de manière irréfutable, la vraisemblance étant suffisante. Le droit à un non-lieu n'est pas garanti conventionnellement et les intérêts de la justice seraient d'ailleurs gravement compromis - et le classement pour motif d'opportunité vidé de sa raison d'être - si les autorités d'instruction étaient tenues de rendre des ordonnances de non-lieu dans des cas pourtant douteux ou de continuer des enquêtes jusqu'au jugement alors qu'il serait préférable d'interrompre ces recherches et d'affecter le personnel disponible à d'autres affaires, dans lesquelles l'exercice de l'action pénale répond à une nécessité plus aiguë ou peut être mené à chef de façon plus efficace. Ainsi, le classement reste la règle et le non-lieu l'exception, celui-ci ne pouvant intervenir que pour des raisons de droit ou si les faits ne constituent pas une infraction (ATF 6B_793/2007 consid. 2).
2. Invoquant l'art. 9 Cst., le recourant estime que la Chambre d'accusation a procédé à une appréciation arbitraire des preuves et ainsi violé l'art. 204 CPP/GE en confirmant le classement prononcé à son encontre. Il lui reproche, en bref, d'avoir retenu des indices à charge et d'avoir ignoré les éléments à décharge.
2.1 La notion d'arbitraire a été rappelée récemment dans l'<ref-ruling> consid. 5.4 auquel on peut donc se référer. Ce grief doit être motivé conformément aux exigences posées par l'<ref-law>. Le recourant doit donc démontrer, sous peine d'irrecevabilité, que la décision attaquée, sur le point contesté, est manifestement insoutenable, et non seulement discutable ou même critiquable (cf. <ref-ruling> consid. 5.4 p. 148).
2.2 Le recourant soutient qu'aucun crédit ne devrait être accordé à l'opinion de son fils vu les relations tendues entre eux.
2.2.1 La Chambre d'accusation a retenu que les déclarations du fils du recourant constituaient un indice à charge et estimé que l'instruction de la cause était insuffisante pour écarter cet élément.
En effet, C._ a expliqué qu'il tenait son père pour parfaitement capable de s'être livré aux actes dénoncés. Il a relevé des similitudes d'écriture ainsi qu'un défaut d'impression sur les photocopies qui correspondait à celui produit par la machine de son père. Enfin, sa propre rente d'invalidité, perçue jusqu'à récemment par son père qui la dépensait, venait de lui être supprimée. L'autorité cantonale a constaté qu'aucune confrontation n'avait eu lieu entre le recourant et son fils pour tirer au clair la question de l'usage et de la suppression de la rente de ce dernier et mesurer le degré de crédibilité des accusations portées contre le recourant, ainsi que, plus largement, pour examiner la nature des relations existant au sein de la famille et l'éventualité des agissements d'un auteur médiat. Elle a également relevé que l'enquête ne comportait pas d'examen précis de la similitude alléguée entre le défaut de qualité des photocopies issues de la machine du recourant et celui constaté sur les courriers litigieux.
2.2.2 Admettant que les relations avec son fils étaient tendues, le recourant n'explique toutefois pas en quoi la motivation précitée serait arbitraire et plus particulièrement en quoi l'enquête menée par les autorités genevoises aurait été exhaustive - notamment sur la suppression de la rente et la crédibilité de C._ - et aurait ainsi permis d'écarter, de manière définitive, les allégations à charge faites par celui-ci. Insuffisamment motivée, la critique est donc irrecevable.
2.3 Le recourant reproche à la Chambre d'accusation d'avoir retenu, comme élément à charge, la similitude entre l'arme photocopiée sur certains courriers litigieux et l'une de sa collection. Il se réfère en particulier au rapport de la police judiciaire du 5 décembre 2007 et au fait que ses armes ont toutes été inventoriées.
2.3.1 L'autorité cantonale a relevé qu'un pistolet de même marque que celui figurant en photocopie sur deux des lettres litigieuses avait été saisi au domicile du recourant, qu'il n'avait pas été possible d'en produire une photocopie à l'aide de la machine se trouvant au domicile de ce dernier, qu'il aurait fallu utiliser une photocopieuse à gros débit et qu'un détail tenant à la position du logo apposé sur l'arme avait fait supposer à la police que celle figurant sur les courriers de menace n'était probablement pas celle trouvée au domicile du recourant. La Chambre d'accusation a toutefois considéré que la similitude relevée constituait tout de même un indice, l'instruction de la cause n'ayant pas permis une analyse très approfondie de cet élément. Elle a relevé en particulier que des montages étaient toujours possibles en matière de photocopies, qu'il se pouvait que l'arme figurant sur deux des courriers de menace ait été photocopiée avec une autre machine, qu'il était d'ailleurs toujours possible d'utiliser le matériel mis à disposition du public dans certains commerces et que rien n'excluait que le recourant ait encore possédé une autre arme de même type vu l'importance de sa collection de provenance souvent non officielle.
2.3.2 Il résulte de la motivation précitée que la Chambre d'accusation n'a nullement ignoré le rapport de la police judiciaire (pièce n° 280). Elle a cependant avancé diverses hypothèses et invoqué le fait que l'enquête n'avait pas été exhaustive pour admettre que la similitude entre des deux armes demeurait malgré tout un indice à charge. Or, le recourant ne démontre pas en quoi les explications fournies par l'autorité - notamment à propos de la possibilité de montages photographiques ou de photocopies au moyen d'autres machines - seraient manifestement erronées, de sorte que sa critique est insuffisante pour faire admettre l'arbitraire allégué.
2.4 Le recourant conteste que son aveu initial puisse être retenu à charge. Il explique avoir avoué certains faits en raison du traumatisme subi lors de sa détention au Sri Lanka.
2.4.1 La Chambre d'accusation a retenu que le recourant avait admis être l'auteur d'un des trois courriers litigieux. Elle a constaté que ce celui-ci était revenu sur ses premiers déclarations, pour des motifs qui tiendraient au sort réservé à l'enquête s'agissant des armes, selon la version des policiers, ou, selon celle du recourant, au mauvais souvenir qu'il avait gardé de sa détention au Sri Lanka. Elle a estimé que ces explications étaient contradictoires et relevé que les policiers n'avaient pas protocolé toutes les déclarations du recourant en raison de leur manque de clarté. Elle a donc conclu que les aveux de l'intéressé ne devaient pas nécessairement être tenus pour invalides et écartés du débat.
2.4.2 Il résulte de cette motivation que la Chambre d'accusation n'a ignoré aucun des éléments avancés par le recourant à propos des motifs de ses premiers aveux. Ce dernier ne conteste toutefois pas l'appréciation cantonale relative aux explications contradictoires données d'une part par la police et d'autre part par lui-même, ni le défaut de verbalisation de certaines déclarations. L'argumentation avancée par le recourant est donc parfaitement impropre à démontrer l'arbitraire dans l'appréciation des preuves telle qu'effectuée par l'autorité précédente.
2.5 Le recourant reproche à la Chambre d'accusation de ne pas avoir retenu les éléments à décharge. Il lui fait grief d'avoir écarté l'expertise graphologique au motif que celle-ci était sommaire. Il se réfère également aux trois courriers adressés aux plaignants, alors que lui-même était en détention, et aux expertises d'ADN qui ne correspondent pas à son profil.
2.5.1 L'autorité cantonale a relevé qu'une analyse graphologique des courriers avait été exécutée et que l'expert avait mis en évidence de nombreuses divergences entre l'écriture du recourant et celle qui figurait sur les courriers de menaces. Elle a toutefois considéré qu'il s'agissait d'un avis sommaire et que l'expert ne motivait pas sa conclusion selon laquelle il était exclu que le recourant ait écrit les trois premiers textes litigieux.
La Chambre d'accusation a également retenu que les trois derniers courriers avaient été acheminés aux plaignants dans des enveloppes fermées, postées le 3 décembre 2007, alors que le recourant était encore incarcéré, qu'il n'était ainsi guère étonnant que l'ADN retrouvé sur les timbres des enveloppes ne fut pas celui du recourant qui n'avait évidemment pas pu les poster. Elle a toutefois considéré que ce constat ne suffisait pas à résoudre la question, l'auteur de ces missives n'ayant pas été identifié. Elle s'est également étonnée que les traces d'ADN retrouvées sur le matériel qui avait contenu les premiers courriers n'eussent pas été comparées avec celles du recourant, nonobstant la mauvaise qualité des échantillons recueillis.
2.5.2 Il résulte de la motivation précitée que les juges précédents ont estimé que l'instruction au sujet de l'expertise graphologique et des courriers de menaces n'avait pas été exhaustive et que ces indices ne permettaient pas d'écarter, de manière absolue, les charges existant à l'encontre du recourant. En effet, d'une part l'expertise graphologique était sommaire, ce qui ressort, sans arbitraire, de la pièce n° 259 du dossier, l'expert précisant qu'un rapport complet pourrait être livré ultérieurement en cas de nécessité. D'autre part, l'auteur des menaces n'a pas été identifié et les traces d'ADN sur les trois premiers courriers n'ont pas été comparées avec celles du recourant, ce que ce dernier ne conteste pas. Le grief est donc vain.
2.6 Sur le vu de ce qui précède, la Chambre d'accusation n'a pas fait preuve d'arbitraire dans l'appréciation des preuves et l'application du droit cantonal en admettant qu'il existait un certain nombre d'indices à charge, ce d'autant plus que l'instruction n'a pas été exhaustive.
3. Invoquant les art. 32 Cst., 6 ch. 2 CEDH et 4 Cst./GE, le recourant se plaint d'une violation de la présomption d'innocence en tant que règle sur le fardeau de la preuve.
3.1 Le recourant ne prétend pas que le droit cantonal invoqué lui offrirait des garanties plus larges que la Constitution et la CEDH. Il suffit donc d'examiner le grief sous l'angle de celles-ci.
En soi, une décision refusant de substituer un non-lieu à un classement n'est pas incompatible avec la présomption d'innocence. Elle peut toutefois soulever un problème sous l'angle de l'art. 6 ch. 2 CEDH lorsque des motifs indissociables du dispositif équivalent en substance à un constat de culpabilité sans établissement préalable de celle-ci, notamment sans que l'intéressé ait eu l'occasion d'exercer les droits de la défense. Si ces derniers ont été respectés, une décision qui ne renferme pas de constat de culpabilité, mais, sur la base des éléments du dossier, se borne à faire état de soupçons, en laissant ouverte la possibilité d'investigations complémentaires, ne viole pas la présomption d'innocence (arrêt de la Cour européenne des droits de l'homme Georg c. Suisse du 8 février 2001, publié in JAAC 2001 n° 133 p. 1379; ATF 1P.341/2004 du 27 juillet 2004 consid. 2).
3.2 Pour les motifs exposés ci-dessus (cf. supra consid. 2), le recourant ne saurait invoquer l'arbitraire quant aux indices retenus à charge. Pour le reste, la motivation cantonale à l'appui du refus du non-lieu ne contient aucun argument de fait ou de droit qui équivaudrait à un constat de culpabilité. Elle se borne à faire état, sur la base des pièces du dossier, des indices à charge et d'indiquer les lacunes de l'instruction dans une cause dont les faits sont loin d'être anodins. On ne discerne, ni dans l'état de fait ni dans la motivation juridique de la décision attaquée, un quelconque passage équivalent à un constat de culpabilité ou donnant à penser que l'autorité cantonale tiendrait le recourant pour coupable. Le grief doit par conséquent être rejeté.
4. Le recours doit être rejeté dans la mesure où il est recevable. Comme il était d'emblée voué à l'échec, l'assistance judiciaire ne saurait être accordée (<ref-law>). Le recourant supportera donc les frais, fixés en fonction de sa situation financière (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire est rejetée.
3. Les frais judiciaires, fixés à 800 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et à la Chambre d'accusation du canton de Genève.
Lausanne, le 12 février 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: La Greffière:
Favre Bendani