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. 