Faits: A. C._, né en 1947, a travaillé jusqu'à l'automne 2003 en qualité d'aide-laborant. Le 30 novembre 2004, il a déposé une demande de rente de l'assurance-invalidité. Après avoir recueilli de nombreuses attestations des médecins traitants, complétées par une première expertise du Centre X._ du 12 juin 2006, laquelle n'a toutefois pas emporté la conviction de l'administration (cf. prise de position du Service médical régional Y._ du 22 octobre 2006), l'Office cantonal AI du Valais a confié un mandat d'expertise médicale à la Clinique Z._, fonctionnant en qualité de COMAI. Dans leur rapport du 10 juillet 2007, les docteurs B._, spécialiste en psychiatrie et psychothérapie, et J._, spécialiste en neurologie, ainsi que M. L._, psychologue FSP et neuropsychologue, ont diagnostiqué une neuropathie périphérique démyélinisante dans le cadre d'une polyradiculonévrite chronique, ainsi qu'un trouble organique du comportement dû à une maladie, une lésion ou à un dysfonctionnement cérébral. Ils ont attesté que sur le plan médico-théorique, des activités procédurales de bureau étaient encore exigibles, dans un horaire de travail à plein temps. Par décision du 25 mars 2008, l'office AI a refusé de prendre en charge un reclassement professionnel car seules des activités simples et répétitives restaient exigibles et l'assuré n'était pas en mesure de suivre une formation, même pratique. Par décision du 4 avril 2008, l'office AI a alloué un quart de rente d'invalidité à compter du 1er octobre 2004, fondé sur un degré d'invalidité de 45 %, voire de 48 %. L'administration a précisé qu'une décision concernant le versement rétroactif pour la période du 1er octobre 2004 au 30 avril 2008 serait établie lorsque toutes les demandes de compensation auraient été traitées. B. C._ a déféré séparément ces décisions au Tribunal cantonal des assurances du canton du Valais. Il a conclu à leur annulation, à la prise en charge de mesures professionnelles, ainsi qu'au versement d'une rente entière d'invalidité depuis le 1er octobre 2004, avec intérêts. Par jugement du 29 octobre 2008, la juridiction cantonale a rejeté les recours, après avoir joint les deux causes. C. C._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, avec suite de frais et dépens, en concluant principalement au versement d'une rente entière ou d'un trois-quarts de rente depuis le 1er mai 2003, à la prise en charge de mesures professionnelles, subsidiairement au renvoi de la cause au tribunal cantonal. L'intimé a conclu au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer. 