Faits:
A. A._ a été interpellé le 26 février 2010 alors qu'il faisait l'objet d'un avis de recherche à la suite d'une agression au couteau survenue le 24 février 2010 au cybercafé "X._" à Genève. Interrogé à deux reprises par la police judiciaire, il a reconnu les faits qui lui étaient reprochés, tout en invoquant la légitime défense. Le 27 février 2010, il a confirmé ses déclarations devant le Juge d'instruction du canton de Genève (ci-après: le Juge d'instruction), lequel a décerné un mandat d'arrêt à son encontre. A._ a été inculpé de tentative de meurtre pour avoir porté un coup de couteau au visage de B._, après une altercation, le coupant profondément de l'oreille droite jusqu'au cou, manquant de toucher une artère vitale.
Le 4 mars 2010, le Juge d'instruction a sollicité de la Chambre d'accusation du canton de Genève (ci-après: la Chambre d'accusation) la prolongation de la détention du prévenu. Le même jour, l'intéressé a demandé sa mise en liberté avant jugement.
Par ordonnance du 5 mars 2010, la Chambre d'accusation a accordé la prolongation sollicitée jusqu'au 5 mai 2010 et refusé la mise en liberté de l'inculpé.
B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral de constater la nullité du mandat d'arrêt délivré par le Juge d'instruction le 27 février 2010, subsidiairement de l'annuler, d'annuler l'ordonnance de prolongation de la détention et de refus de mise en liberté du 5 mars 2010 et d'ordonner sa remise en liberté immédiate. Subsidiairement, il conclut à ce qu'il soit procédé à l'établissement des faits pertinents qui seraient contestés par les parties adverses, notamment par l'audition du commissaire de police M. V. et de l'inspecteur S., en application de l'<ref-law>. Il requiert en outre l'assistance judiciaire. Il se plaint pour l'essentiel d'une violation de l'art. 6 CEDH, invoquant un droit à "l'avocat de la première heure", et d'une violation de son droit d'être entendu.
La Chambre d'accusation se réfère aux considérants de sa décision. Le Procureur général s'en rapporte à l'appréciation du Tribunal fédéral s'agissant de la recevabilité du recours et, sur le fond, conclut à son rejet. Le recourant a répliqué le 12 avril 2010; il a complété l'état de faits de son recours et annexé de nouvelles pièces.

Considérant en droit:
1. 1.1 La décision attaquée, qui ordonne la prolongation de la détention préventive du recourant pour une durée de deux mois, peut faire l'objet d'un recours en matière pénale au sens des <ref-law>. Formé en temps utile (<ref-law>) contre une décision prise en dernière instance cantonale (<ref-law>) et qui touche le recourant dans ses intérêts juridiquement protégés (art. 81 al. 1 let. a et b ch. 1 LTF), le recours est recevable.
1.2 Le recourant a annexé plusieurs pièces nouvelles à sa réplique du 12 avril 2010, à savoir notamment les copies de deux convocations pour des audiences agendées à Genève les 3 et 4 mars 2010. Ces preuves nouvelles ne peuvent pas être prises en considération au regard de l'<ref-law>, ce d'autant que le recourant ne fait pas valoir que celles-ci résulteraient de l'arrêt attaqué (<ref-law> in fine). D'ailleurs, elles n'étaient de toute manière pas de nature à influer sur le sort de la présente procédure.
2. La Chambre d'accusation a considéré en substance qu'il existait des charges suffisantes de tentative de meurtre, voire lésions corporelles, à l'encontre du recourant et que les risques de récidive et de fuite étaient réalisés. Par ailleurs, même si la Cour européenne des droits de l'homme avait admis un droit à un avocat dès la première heure, elle n'en avait toutefois pas déduit que la mise en détention avait été illégale. Dans le canton de Genève, une telle garantie n'existait pas encore, mais le prévenu conservait le droit de se taire, ce dont il avait été informé en prenant connaissance de l'art. 107A du code de procédure pénale cantonal genevois (ci-après: CPP/GE). En outre, il n'y avait pas de violation du droit d'être entendu du fait de la détention de l'inculpé dans une autre prison que Champ-Dollon.
Le recourant ne remet pas en cause les motifs de la détention. En revanche, il fait valoir que l'art. 6 par. 3 let. c CEDH garantit le droit à un avocat dès le premier interrogatoire de police. Or, il n'a pas bénéficié de l'assistance d'un défenseur durant la garde à vue et n'a pas renoncé valablement à la visite d'un avocat, puisqu'il n'avait pas été informé de ce droit par l'officier de police. Ce vice devait donc conduire à la constatation de la nullité du mandat d'arrêt et à sa libération immédiate. De plus, il a été transféré à la prison préventive de Sion, qui se trouve à plus de deux heures de Genève, et le Palais de justice ne dispose pas de locaux permettant aux clients de s'entretenir avec leur mandataire. N'ayant pas pu rencontrer son avocat avant l'audience de la Chambre d'accusation, son droit d'être entendu a été violé.
3. 3.1 Selon l'art. 23 let. a de la Constitution genevoise, tout inculpé doit, au début de la première comparution devant le juge d'instruction, être expressément informé de son droit de se faire assister par un défenseur. L'<ref-law>/GE précise que l'inculpé a le droit d'obtenir la visite d'un avocat et de conférer librement avec lui, dès la fin de son interrogatoire par l'officier de police, mais au plus tard à la première heure ouvrable à l'issue des 24 heures suivant le début de son audition par la police. A l'instar de la plupart des autres cantons, le droit cantonal genevois n'autorise pas le défenseur à être présent dès le stade des interrogatoires du prévenu par la police, dans le cadre de la procédure d'investigation.
Cette situation changera avec l'entrée en vigueur, le 1er janvier 2011, du Code de procédure pénale suisse (CPP; FF 2007 6583), qui consacre le droit à un "avocat de la première heure". Aux termes de l'art. 158 al. 1 let. c CPP, au début de la première audition, la police ou le ministère public informent le prévenu dans une langue qu'il comprend qu'il a le droit de faire appel à un défenseur ou de demander un défenseur d'office. Les auditions effectuées sans que ces informations aient été données ne seront pas exploitables (<ref-law>). A l'heure actuelle toutefois, aucune disposition de droit fédéral ne garantit un droit à l'avocat de la première heure.
Le recourant ne reproche pas à la Chambre d'accusation d'avoir mal appliqué le droit cantonal ou fédéral. Il estime cependant qu'en refusant de constater que son droit à un avocat de la première heure n'avait pas été respecté, la Chambre d'accusation a violé l'art. 6 CEDH et sa mise en détention serait de ce fait illégale.
3.2 En vertu de l'art. 6 par. 3 let. c CEDH, tout accusé a notamment droit à se défendre lui-même ou avoir l'assistance d'un défenseur de son choix. Cette garantie constitue un aspect particulier du droit au procès équitable au sens de l'art. 6 par. 1 CEDH. Selon la jurisprudence récente de la Cour européenne des droits de l'homme, cette disposition confère à l'accusé le droit de bénéficier de l'assistance d'un avocat dès les premiers stades des interrogatoires de police, sauf à démontrer, à la lumière des circonstances particulières de l'espèce, qu'il existe des raisons impérieuses de restreindre ce droit. Même dans ce dernier cas, pareille restriction - quelle que soit sa justification - ne doit pas indûment préjudicier aux droits découlant pour l'accusé de l'art. 6 CEDH; il est en principe porté une atteinte irrémédiable aux droits de la défense lorsque des déclarations incriminantes faites lors d'un interrogatoire de police subi sans assistance possible d'un avocat sont utilisées pour fonder une condamnation (arrêt de la Cour européenne des droits de l'homme Salduz c. Turquie du 27 novembre 2008 par. 50 ss). Dans l'affaire Salduz c. Turquie, la Cour européenne des droits de l'homme a constaté une violation de l'art. 6 par. 3 let. c CEDH, le droit du requérant à bénéficier de l'assistance d'un avocat ayant été restreint pendant sa garde à vue. Ni l'assistance fournie ultérieurement par un avocat ni la nature contradictoire de la suite de la procédure n'avaient pu porter remède à cette atteinte. Il n'appartenait toutefois pas à la Cour de spéculer sur l'impact qu'aurait eu sur l'aboutissement de la procédure la possibilité pour le requérant de se faire assister par un avocat dès son arrestation (arrêt précité Salduz c. Turquie, par. 58). La forme la plus appropriée de redressement était, pourvu que le requérant le demande, un nouveau procès conforme aux exigences de l'art. 6 par. 1 CEDH.
Jusqu'à présent, le Tribunal fédéral s'est refusé à inférer directement de l'art. 6 par. 3 CEDH un droit pour le prévenu de communiquer librement avec son défenseur immédiatement après son arrestation (<ref-ruling>; arrêt 1P.556/2006 du 25 janvier 2007; arrêt 6B_700/2009 du 26 novembre 2009). La question de savoir si ce point devrait actuellement être résolu différemment peut rester indécise en l'espèce, puisque le constat d'une éventuelle violation de l'art. 6 CEDH ne permettrait de toute façon pas d'arriver à une solution différente de celle retenue par la Chambre d'accusation.
4. 4.1 En l'espèce, le recourant fait valoir qu'il n'a pas été informé de son droit de se faire assister d'un avocat durant sa garde à vue et au cours des interrogatoires de police, puisque l'<ref-law>/GE ne prévoit pas cette possibilité. Il ressort du dossier que, lors de ces interrogatoires, le prévenu a reconnu les faits qui lui étaient reprochés, tout en contestant son intention de tuer. Devant le Juge d'instruction, il a confirmé ses déclarations. L'intéressé n'indique pas qu'il aurait tenu, devant la police, des propos incriminants qu'il aurait ensuite réfutés et qui pourraient lui porter préjudice dans le cadre de la détention préventive ou du jugement au fond. Dans ces conditions, il semble douteux qu'il ait un intérêt à faire constater une violation de son droit à un procès équitable. Quoi qu'il en soit, même si un droit à un avocat de la première heure devait être reconnu au recourant en vertu de l'art. 6 par. 3 let. c CEDH, et que ce droit n'avait pas été respecté, il ne s'ensuit pas pour autant que le mandat d'arrêt décerné à son encontre serait entaché de nullité et qu'il devrait être libéré immédiatement (cf. consid. 4.2 ci-dessous).
Le recourant se plaint également qu'il n'a pas renoncé valablement à son droit de consulter un avocat à l'issue de son audition par l'officier de police le 27 février 2010 à 11h48. Il soutient que, étant analphabète, il n'a pas pu lire les questions figurant sur le procès-verbal d'interrogatoire, qui lui rappelaient les droits prévus à l'<ref-law>/GE. L'officier de police a alors indiqué "non" à la question de savoir s'il souhaitait obtenir la visite d'un avocat et conférer librement avec lui, sans toutefois lui relire le questionnaire. Ce point n'a toutefois pas besoin d'être élucidé, puisque le recourant a de nouveau été informé de ses droits au début de son audition devant le Juge d'instruction, le même jour à 18h35, et qu'il a alors demandé la désignation d'un avocat d'office, acceptant néanmoins d'être interrogé en l'absence d'un mandataire. Il sied dès lors de constater que le prévenu n'a pas renoncé à son droit de consulter un avocat et que les droits de la défense ont été respectés, contrairement à ce qu'il semble prétendre.
4.2 L'éventuelle violation de l'art. 6 par. 3 let. c CEDH n'a pas pour conséquence, comme le soutient le recourant, que le mandat d'arrêt décerné à son encontre, de même que sa détention, ne serait pas valide. En effet, si une garantie procédurale n'a pas été respectée, il convient autant que possible de remettre la personne lésée dans la situation qui aurait été la sienne si l'exigence en cause n'avait pas été méconnue. S'agissant d'une violation du droit d'être entendu par exemple, la réparation consiste à renvoyer le dossier à l'autorité intimée pour qu'elle rende une nouvelle décision après avoir donné à la personne intéressée l'occasion de s'exprimer. Ceci n'est toutefois pas possible dans le cas de l'art. 6 par. 3 let. c CEDH, puisque la "première heure" est passée et que ni l'assistance fournie ultérieurement par un avocat ni la nature contradictoire de la suite de la procédure ne peuvent porter remède à cette atteinte. La Cour européenne des droits de l'homme a ainsi considéré que, dans une telle situation, la forme la plus appropriée de redressement était, pourvu que le requérant le demande, un nouveau procès conforme aux exigences de l'art. 6 par. 1 CEDH; la Cour s'est au demeurant abstenue de spéculer sur l'impact qu'aurait eu sur l'aboutissement de la procédure au fond la possibilité pour le requérant de se faire assister par un avocat dès son arrestation, ni a fortiori sur les conditions de la détention préventive.
Il apparaît dès lors que la mise en détention provisoire n'est pas pour autant illégale. Il ne serait en effet guère concevable qu'un prévenu sur lequel pèsent des soupçons suffisants de culpabilité et un risque concret de fuite, de collusion ou de réitération, puisse échapper à une détention préventive matériellement justifiée et, le cas échéant, se soustraire à la justice pour des raisons formelles. Le vice allégué ne saurait donc avoir pour conséquences l'invalidation du mandat d'arrêt et la libération immédiate du recourant, ce d'autant que ce dernier n'a pas remis en cause les conditions matérielles de sa détention. On peut en outre relever que le mandat d'arrestation ne s'appuie pas uniquement sur les déclarations faites par le recourant devant la police, mais également sur d'autres éléments du dossier, à savoir notamment ses aveux devant le Juge d'instruction, les images de la caméra de surveillance du cybercafé "X._", la plainte du lésé ainsi que les déclarations de plusieurs témoins directs.
5. Le recourant se plaint finalement d'une violation de son droit d'être entendu du fait de son transfert à Sion le 28 février 2010. Son mandataire, constitué pour la défense de ses intérêts le 1er mars 2010, n'a pas pu lui rendre visite le lendemain puisqu'il n'avait pas encore obtenu l'accord formel du Juge d'instruction, comme l'exige la pratique valaisanne. Les 3 et 4 mars 2010, le défenseur du recourant avait des audiences ou des rendez-vous à Genève qui l'ont empêché de faire le déplacement à Sion. Ensuite, comme le Palais de justice ne dispose pas de locaux permettant aux clients de s'entretenir avec leur mandataire, le recourant n'a pas eu la possibilité de rencontrer son avocat avant l'audience de la Chambre d'accusation et n'a de ce fait pu exercer ses droits de façon efficace.
Comme l'a relevé à juste titre la Chambre d'accusation, la détention de l'inculpé dans une autre prison que Champ-Dollon et les difficultés que cette situation pouvait entraîner pour son conseil dans l'exercice de son droit de visite ne constituent pas une violation du droit d'être entendu. On peut mentionner que l'avocat du recourant bénéficiait de deux jours ouvrables pour rendre visite à son client, ce qui apparaît amplement suffisant, même en considérant que le prévenu était détenu en Valais et qu'il fallait compter environ cinq heures de voyage pour le déplacement. Ainsi que le fait remarquer le Ministère public du canton de Genève dans ses observations, il n'appartient pas aux autorités judiciaires de gérer les agendas des avocats. Si le mandataire du recourant estimait ne pas être en mesure de remplir son mandat pour des questions liées à une surcharge de travail temporaire, il lui revenait alors de solliciter la nomination d'un autre avocat ou de sous-mandater un confrère.
6. Il résulte de ce qui précède que le recours, entièrement mal fondé, doit être rejeté. Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Le recourant requiert la désignation de Me Jean-Pierre Garbade en qualité d'avocat d'office. Il y a lieu de faire droit à cette requête et de fixer d'office les honoraires de l'avocat, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est admise. Me Jean-Pierre Garbade est désigné comme avocat d'office du recourant et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué au mandataire du recourant, au Juge d'instruction, au Ministère public et à la Chambre d'accusation du canton de Genève.
Lausanne, le 19 avril 2010
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Mabillard