Faits:
A. X._ est né en Somalie en 1978. Ses parents sont séparés. Il est arrivé en Suisse avec sa mère le 10 octobre 1994. Sa demande d'asile a été rejetée le 24 novembre 1994. Il a été mis au bénéfice d'une admission provisoire. Après avoir appris le français à l'école pendant une année, il a cessé toute formation depuis l'âge de 17 ans.
Il a fait l'objet d'une première série de condamnations:
- quatre mois d'emprisonnement avec sursis pendant trois ans prononcés le 11 décembre 1996 pour lésions corporelles, vol d'usage, circulation sans permis, vol, dommage à la propriété et violation de domicile
- placement en maison d'éducation à A._ prononcé le 6 mars 1998 pour deux brigandages et infractions à la loi sur la circulation routière, à quoi s'ajoutaient l'expulsion pour une durée de 15 ans et la révocation du précédent sursis.
En septembre 1999, à sa sortie de A._, où il avait entrepris une formation de menuisier, il a alterné emplois de courtes durées et périodes de chômage.
Par décision du 13 décembre 2000, l'Office fédéral des réfugiés (devenu l'Office fédéral des migrations) a prononcé la levée de l'admission provisoire de X._. Cette décision est entrée en force. L'intéressé a indiqué qu'il entreprenait des démarches pour obtenir un passeport somalien.
B. Le 23 avril 2002, Y._, de nationalité suisse, a donné naissance à un garçon nommé Z._ que X._ a plus tard reconnu. Le 2 mai 2003, X._ et Y._ ont contracté mariage. Le second enfant du couple, prénommé B._, est né à C._ en 2003.
Le 1er décembre 2003, l'Office cantonal de la population a délivré à X._ une autorisation de séjour au titre de regroupement familial, régulièrement renouvelée jusqu'au 22 mai 2005.
X._ a fait l'objet d'une deuxième série de condamnations:
- six jours d'arrêts prononcés le 2 septembre 2003 pour tentative d'escroquerie d'importance mineure et obtention frauduleuse d'une prestation;
- dix jours d'emprisonnement avec sursis pendant deux ans prononcés le 2 novembre 2004 pour conduite en état d'ivresse et dommage à la propriété;
- trente jours d'emprisonnement prononcés le 16 décembre 2004 pour lésions corporelles simples et dommages à la propriété sur plainte de son épouse ainsi que pour violence ou menace contre les fonctionnaires, après que les époux X._ et Y._ aient décidé de vivre séparément depuis le mois de novembre 2004;
- trois ans et demi de réclusion prononcés le 20 octobre 2006 pour tentative de meurtre sur un tiers le 21 octobre 2005 à l'aide d'un couteau. A cette occasion, les experts ont constaté que l'intéressé était dépendant du cannabis et de l'alcool, raison pour laquelle un trai-tement ambulatoire a été ordonné pour le guérir de sa dépendance à l'alcool.
X._ a été incarcéré à la prison de D._ depuis le 21 octobre 2005.
Par jugement du 15 décembre 2006, le Tribunal de première instance a prononcé le divorce des époux X._ et Y._.
Dans un rapport du 3 avril 2007 adressé à l'Office cantonal de la population, le Service de la protection des mineurs a déclaré que le père et ses enfants entretenaient des liens affectifs réciproques appréciés par la mère et la grand-mère maternelle des enfants. Pour le bon développement de ces derniers, il semblait essentiel que le père puisse rester en Suisse.
Par décision du 4 septembre 2007, l'Office cantonal de la population a adressé à X._ une menace d'expulsion administrative fondée sur les dernières condamnations prononcées à son encontre, mais acceptait de lui donner une dernière chance. Cette décision est entrée en force.
Le 16 novembre 2007, l'intéressé a demandé la prolongation de son permis de séjour.
Le 20 novembre 2007, l'intéressé a participé à une bagarre après avoir consommé de l'alcool et deux jours plus tard s'est vu reprocher une arrivée tardive durant son régime de semi-liberté auprès de la Maison E._. Le rapport établi le 29 novembre 2007 par la direction des établissements pénitentiaires F._ relevait que l'intéressé avait fait preuve d'un comportement et d'une attitude corrects tant en général que dans son travail et qu'il avait entrepris de s'acquitter de l'indemnité due au titre de tort moral subi par sa victime. Le rapport établi le 29 novembre 2007 de la Maison E._ signalait cependant que le comportement de l'intéressé n'était pas exempt de reproches en raison de son addiction à l'alcool.
Par jugement du 1er février 2008, le Tribunal d'application des peines et mesures a refusé la libération conditionnelle de l'intéressé au vu de ses nombreux antécédents, de ses projets d'avenir peu concrets et de sa consommation d'alcool qui le rendait violent.
C. Par décision du 1er février 2008, l'Office cantonal de la population a refusé de renouveler l'autorisation de séjour de X._ en raison des nombreuses condamnations dont il avait fait l'objet, la dernière pour une tentative de meurtre, ainsi que de son absence d'intégration sociale et professionnelle. L'intérêt public à son éloignement de Suisse l'emportait sur la présence en Suisse de sa seule famille et de ses enfants, même s'il maintenait avec eux des relations étroites.
Par mémoire du 3 mars 2008, X._ a interjeté recours contre cette décision.
D. Par décision du 4 novembre 2008, la Commission cantonale de recours de police des étrangers du canton de Genève a rejeté le recours déposé par l'intéressé contre la décision rendue le 1er février 2008 par l'Office cantonal de la population. Son mariage avait été dissous avant d'avoir duré cinq ans. Ses relations avec ses enfants ne suffisaient pas à faire prévaloir son intérêt privé à rester en Suisse sur l'intérêt public à son éloignement dès lors que son comportement et les condamnations subies démontraient son incapacité à respecter l'ordre public.
E. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler la décision rendue le 4 novembre 2008 par la Commission cantonale de recours et sollicite le renouvellement de son autorisation de séjour. Il dépose une demande d'assistance judiciaire et la nomination comme défenseur d'office de son mandataire. Il se plaint de la violation de l'art. 8 CEDH.
La Commission de recours et l'Office cantonal de la population ont renoncé à déposer des observations. L'Office fédéral des migrations conclut au rejet du recours.

Considérant en droit:
1. La loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 p. 113) a été abrogée lors de l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; loi sur les étrangers RS 142.20; cf. ch. I de l'annexe à l'art. 125 LEtr). Toutefois, comme la demande du recourant a été déposée avant l'entrée en vigueur de la nouvelle loi, elle est régie par l'ancien droit (art. 126 al. 1 LEtr).
2. 2.1 D'après l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit.
2.2 Un étranger peut, selon les circonstances, se prévaloir du droit au respect de sa vie privée et familiale garanti par l'art. 8 par. 1 CEDH pour s'opposer à l'éventuelle séparation de sa famille. Encore faut-il, pour pouvoir invoquer cette disposition, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse (nationalité suisse ou autorisation d'établissement) soit étroite et effective (<ref-ruling> consid. 3.1 p. 285; <ref-ruling> consid. 5.3.1 p. 211). L'art. 8 CEDH s'applique lorsqu'un étranger fait valoir une relation intacte avec ses enfants bénéficiant du droit de résider en Suisse, même si ces derniers ne sont pas placés sous son autorité parentale ou sous sa garde du point de vue du droit de la famille (<ref-ruling> consid. 1d p. 3; <ref-ruling> consid. 1c p. 84; <ref-ruling> consid. 1c p. 157 et les références).
En l'espèce, les fils du recourant, qui sont mineurs et vivent aux côtés de leur mère, sont ressortissants suisses. Dans son arrêt, l'instance précédente a constaté que le recourant exerce un droit de visite sur ses fils. Dans la mesure où l'arrêt attaqué a des incidences sur ses relations personnelles avec ses fils, le recourant peut donc se prévaloir de l'art. 8 CEDH.
2.3 Déposé en temps utile et dans les formes prescrites par la loi par le destinataire de l'arrêt attaqué, le présent recours en matière de droit public est en principe recevable (cf. <ref-law>) en tant qu'il concerne le grief de violation de l'art. 8 CEDH (<ref-law>).
3. 3.1 Le droit au respect de la vie privée et familiale garanti par l'art. 8 par. 1 CEDH n'est pas absolu. Une ingérence dans l'exercice de ce droit est possible selon l'art. 8 par. 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale, ou à la protection des droits et libertés d'autrui. La question de savoir si, dans un cas d'espèce, les autorités de police des étrangers sont tenues d'accorder une autorisation de séjour fondée sur l'art. 8 CEDH doit être résolue sur la base d'une pesée de tous les intérêts privés et publics en présence (<ref-ruling> consid. 2e p. 639; <ref-ruling> consid. 3c p. 5; arrêt 2C_693/2008 du 2 février 2009, consid. 2.1 destiné à la publication).
En ce qui concerne l'intérêt public, il faut retenir que la Suisse mène une politique restrictive en matière de séjour des étrangers, pour assurer un rapport équilibré entre l'effectif de la population suisse et celui de la population étrangère résidante, ainsi que pour améliorer la situation du marché du travail et assurer un équilibre optimal en matière d'emploi (cf. art. 16 LSEE et 1er de l'ordonnance du 6 octobre 1986 limitant le nombre des étrangers [OLE; RO 1986 p. 1791] abrogée depuis l'entrée en vigueur du nouveau droit des étrangers, cf. consid. 1 ci-dessus). Ces buts sont légitimes au regard de l'art. 8 par. 2 CEDH (<ref-ruling> consid. 2a p. 67; <ref-ruling> consid. 3c p. 298; arrêt 2C_693/2008 du 2 février 2009, consid. 2.2 destiné à la publication).
Pour ce qui est de l'intérêt privé à obtenir une autorisation de séjour, il faut constater que l'étranger disposant d'un droit de visite sur son enfant habilité à résider en Suisse peut en principe exercer ce droit même s'il vit à l'étranger, au besoin en aménageant ses modalités quant à la fréquence et à la durée. Un droit plus étendu peut exister en présence de liens familiaux particulièrement forts dans les domaines affectif et économique et lorsque, en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, cette relation ne pourrait pratiquement pas être maintenue; en outre, le parent qui entend se prévaloir de cette garantie doit avoir fait preuve en Suisse d'un comportement irréprochable (<ref-ruling> consid. 3c p. 5, 22 consid. 4a p. 25; arrêts 2C_231/2008 du 2 juillet 2008, 2C_340/2008 du 28 juillet 2008 et les références citées). Un comportement est irréprochable s'il n'existe aucun motif en droit des étrangers d'éloigner ce parent ou de le maintenir à l'étranger, en d'autres termes, s'il ne s'est rendu coupable d'aucun comportement réprimé par le droit des étrangers ou le droit pénal. Il faut en outre considérer qu'il existe un lien affectif particulièrement fort lorsque le droit de visite est organisé de manière large et qu'il est exercé de manière régulière, spontanée et sans encombre (arrêt 2A.550/2006 du 7 novembre 2006, consid. 3.1 et les références citées).
3.2 En l'espèce, selon le rapport du Service de protection de l'enfance du 3 avril 2007, le recourant a reçu la visite de ses fils avant et durant son incarcération. Selon le rapport, les relations entre eux sont bonnes et appréciées par la mère et la grand-mère maternelle des enfants. Il ressort aussi des déclarations du recourant qu'il s'acquitte régulièrement, lorsqu'il en a les moyens, de la pension due à ses enfants. Sur la base de ces éléments, on ne saurait pourtant considérer que les liens affectifs et économiques qui unissent le recourant à ses fils sont étroits, même s'ils semblent l'être plus sur le plan affectif qu'économique. Les liens économiques ne semblent pas devoir se renforcer compte tenu de l'incapacité passée du recourant de conserver une place professionnelle stable. L'encadrement rigide qui régit son actuel travail au sein du service de voirie de la Maison E._ ne permet pas encore de poser un pronostic favorable quant à l'avenir économique du recourant. Dans ces conditions, on peut douter que les liens affectifs et économiques qui unissent le recourant à ses fils puissent être qualifiés de particulièrement forts au sens où l'entend la jurisprudence.
Quoi qu'il en soit, il n'est pas nécessaire d'examiner plus précisément cet élément du moment que le comportement du recourant n'est de loin pas irréprochable. Celui-ci a subi une première série de condamnations entre 1996 et 1998, puis une nouvelle série de quatre condamnations entre 2003 et 2006, la dernière peine prononcée de trois ans et demi de réclusion sanctionnant une tentative de meurtre par dol éventuel à l'aide d'un couteau. A cela s'ajoute que les experts qui se sont penchés sur le comportement du recourant ont constaté qu'il était dépendant à l'alcool et au cannabis. Malgré une dernière chance accordée par l'Office cantonal de la population par décision du 4 septembre 2007, le recourant, qui suivait une thérapie ambulatoire pour traiter son addiction, a participé à une bagarre sous l'emprise de l'alcool le 20 novembre 2007 à E._. Il est possible qu'entre-temps son comportement n'ait plus fait l'objet de reproche. Il faut toutefois remarquer que l'absence de reproche à l'égard du recourant, qui est encore soumis à un régime carcéral de semi-détention, ne constitue pas un élément notable qui plaide spécialement en sa faveur. Enfin, ce dernier n'a pas démontré qu'il était abstinent, quand bien même il est conscient que la consommation d'alcool peut l'amener à commettre de nouveaux actes de violences. Le simple fait de travailler auprès du service de voirie de l'établissement pénitentiaire dans lequel il finit sa semi-détention ne démontre pas encore sa capacité à s'intégrer dans la société. La gravité des actes réprimés et l'absence de pronostic favorable conduisent à privilégier l'intérêt public au maintien de l'ordre en Suisse par rapport à celui du recourant d'obtenir un permis de séjour aux fins de conserver des relations personnelles avec ses fils au sens de l'art. 8 CEDH.
4. Les considérants qui précèdent conduisent au rejet du recours.
Les conclusions du recourant apparaissant d'emblée dénuées de chance de succès, sa requête d'assistance judiciaire doit être rejetée (art. 64 al LTF a contrario). Les frais de justice seront fixés compte tenu de sa situation financière (<ref-law>). Succombant, le recourant n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population et à la Commission cantonale de recours de police des étrangers du canton de Genève, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 26 mars 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Dubey