Faits: A. X._, ressortissant des Etats-Unis, est né en 1946. Il se qualifie d'homme d'affaires et affirme être à la tête de plusieurs sociétés actives dans des domaines variés. En 1999, B._ a été approché par X._ en vue de la vente de sucre à la Russie. Dès 2000, au cours de diverses transactions, le second a sollicité du premier, qui agissait par le biais de sa société A._ SA, d'importants versements dans le but d'obtenir des garanties bancaires et de couvrir ses frais pour trouver des acheteurs en Russie. En réalité, X._ a utilisé essentiellement ces fonds à des fins personnelles. B. Par arrêt du 20 mai 2005, la Cour correctionnelle avec jury du canton de Genève a condamné X._, par défaut, à la peine de 30 mois d'emprisonnement et à 5 ans d'expulsion du territoire suisse, pour abus de confiance portant sur un montant total de plus de 7 millions de dollars. B.a A l'audience de jugement, avant la clôture des débats, la Présidente de la Cour correctionnelle a informé les parties qu'elle entendait poser, en application de l'art. 299 aCPP/GE, la question complémentaire de l'abus de confiance. B.b L'avocat de X._ a procédé à une dictée au procès-verbal et conclu qu'il n'y avait pas lieu de poser cette question, celle-ci visant une infraction complètement différente de celle retenue dans l'ordonnance de renvoi, ce qui constituait une violation flagrante du droit d'être entendu, du principe du procès équitable consacré par l'art. 6 CEDH et des dispositions cantonales de procédure. B.c La Présidente a ensuite prononcé la clôture des débats et ordonné que la question de l'abus de confiance soit posée à chacune des questions principales. C. Par arrêt du 31 octobre 2008, la Cour de cassation genevoise a rejeté le pourvoi de X._. D. Ce dernier dépose un recours en matière pénale au Tribunal fédéral. Invoquant une violation des art. 29 al. 2, 32 al. 2 Cst. et 6 ch. 3 let. a et b CEDH, il conclut à l'annulation de l'arrêt cantonal et au renvoi de la cause à la Cour de cassation pour qu'elle annule le jugement de première instance et retourne la procédure à la Cour correctionnelle qui devra statuer à nouveau dans le sens des considérants. Il requiert également l'assistance judiciaire. La Cour de cassation a renoncé à déposer des observations. Le Procureur général et l'intimée ont conclu au rejet du recours. 