Faits: A. A._ a été interpellé le 1er février 2010 dans le canton de Saint-Gall alors qu'il s'apprêtait à passer la frontière autrichienne au volant d'une voiture volée. Il a été interrogé par la police cantonale et par le Juge d'instruction du canton de Saint-Gall avant d'être transféré dans le canton de Genève. Le 3 février 2010, il a été auditionné par la police judiciaire genevoise et le lendemain il a été entendu par le Juge d'instruction du canton de Genève, qui a décerné un mandat d'arrêt à son encontre. Il a été inculpé de vol pour avoir, à Genève, dans la nuit du 30 au 31 janvier 2010, dérobé un véhicule LEXUS LS 600 h d'une valeur de 140'000 fr. stationné devant le garage Emil Frey. Sa détention a été prolongée une première fois le 12 février 2010 pour une durée d'un mois. Le 11 mars 2010, le Procureur général du canton de Genève a requis la prolongation de la détention du prévenu pour une durée de trois mois. Par ordonnance du 12 mars 2010, la Chambre d'accusation du canton de Genève (ci-après: la Chambre d'accusation) a accordé la prolongation sollicitée jusqu'au 12 avril 2010. B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral de déclarer nulle l'ordonnance de la Chambre d'accusation du 12 mars 2010, d'ordonner sa mise en liberté ainsi que le retrait du dossier de tous les procès-verbaux établis depuis le 1er janvier 2010 par les différentes autorités qui l'ont interrogé et de constater la nullité du mandat d'arrêt décerné le 4 mars 2010. A titre subsidiaire, il conclut à l'annulation de l'ordonnance attaquée et, plus subsidiairement, au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Il requiert en outre l'effet suspensif, sa mise en liberté immédiate jusqu'à droit jugé au fond et 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". La Chambre d'accusation se réfère aux considérants de sa décision. Le Procureur général s'en rapporte à justice quant à la recevabilité du recours et, sur le fond, fait siens les motifs invoqués par la Chambre d'accusation. Le recourant a indiqué, le 1er avril 2010, qu'il renonçait à répliquer. Par ordonnance du 7 avril 2010, la Chambre d'accusation a prolongé une nouvelle fois la détention du recourant jusqu'au 17 juin 2010. 