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.

Considérant en droit:
1. Le litige porte sur le droit du recourant à des prestations de l'AI.
Les premiers juges ont exposé correctement les règles applicables. Il suffit de renvoyer au jugement attaqué.
2. 2.1 Le recourant soutient que l'étendue de sa capacité de travail n'a pas été appréciée correctement. Il se plaint en particulier d'une constatation inexacte et incomplète des faits pertinents ainsi que d'une violation de son droit d'être entendu. A cet égard, le recourant rappelle qu'il avait vainement requis de l'office intimé la quête d'un rapport complémentaire auprès du psychiatre B._ et du psychologue L._ (auteurs de l'expertise de psychiatrie et de neuropsychologie du 10 juillet 2007), afin qu'ils précisent si des activités dans le domaine de l'industrie légère, le conditionnement et la surveillance pourraient être exercées. Quant aux premiers juges, ils leur reproche de n'avoir pas administré eux-mêmes ce complément d'instruction à défaut de l'avoir confié à l'office intimé.
2.2 Les juges cantonaux ont exposé les motifs qui les ont conduits à juger la cause en l'état sans mettre en oeuvre la mesure d'instruction litigieuse, répondant ainsi au grief que le recourant avait déjà soulevé en première instance. En effet, ils ont rappelé que le recourant n'était nullement limité dans diverses activités, au nombre desquelles figurent des travaux répétitifs de bureau. A cet égard, l'appréciation du tribunal cantonal ne saurait être qualifiée d'arbitraire dès lors qu'elle se fonde sur les conclusions claires du rapport d'expertise interdisciplinaire du COMAI du 10 juillet 2007 (ch. 1 p. 17), co-signé par les deux experts prénommés (B._ et L._). Le moyen se révèle ainsi mal fondé.
3. 3.1 Le recourant se plaint ensuite de n'avoir pas bénéficié de mesures professionnelles du 1er octobre 2003 au 30 avril 2008, période durant laquelle il était incapable de travailler. Il en déduit que la décision administrative du 25 mars 2008 et le jugement attaqué devraient en conséquence être annulés en raison de cette carence.
3.2 A ce sujet, la juridiction cantonale a constaté que le recourant ne se trouve pas en état de suivre avec succès des mesures de formation professionnelle ou pratique. Elle a ainsi admis que l'intimé avait nié à juste titre le droit à un reclassement, en précisant que le droit à une aide au placement avait été réservé.
Le recourant ne conteste pas le bien-fondé de ce constat de fait. Il serait dès lors contraire au droit d'ordonner à l'intimé de prendre à sa charge des mesures d'emblée vouées à l'échec.
4. 4.1 Le recourant s'en prend aussi au revenu d'invalide qui a été établi sur la base des statistiques salariales pour évaluer le degré de son invalidité. Il soutient que les calculs de l'administration sont optimistes et qu'ils devraient être corrigés en conséquence, afin qu'un trois-quarts de rente, ou à tout le moins une demi-rente lui soit accordé.
4.2 Ce grief est dénué de substance. En effet, le recourant n'expose pas en quoi la prise en compte des statistiques tirées de l'Enquête sur la structures des salaires violerait le droit, aussi bien quant au principe (cf. <ref-ruling>) que dans leur application concrète au cas d'espèce.
5. 5.1 Le recourant reproche encore au tribunal cantonal d'avoir fixé le début du droit à la rente au 1er mai 2008, alors que son incapacité de travail remonte au mois d'octobre 2003. Il soutient par ailleurs que son taux d'invalidité atteint 70 %, ce qui doit ouvrir le droit à une rente entière.
5.2 Les reproches du recourant sont mal fondés quant au point de départ du versement de la rente, car à teneur de la décision administrative (dont le dispositif a été confirmé par le jugement attaqué), la rente n'est pas servie à partir du 1er mai 2008 mais à compter du 1er octobre 2004, soit un an après le moment où la capacité travail a été réduite (le 20 octobre 2003). Les conclusions du recourant, qui revendique le paiement de la rente à compter du 1er mai 2003 déjà, sont non seulement dépourvues de motivation mais aussi infondées (voir l'<ref-law>, dans sa teneur en vigueur jusqu'au 31 décembre 2007).
Par ailleurs, le recourant n'expose pas en quoi le jugement attaqué procéderait d'une violation du droit dans la mesure où le degré d'invalidité a été fixé à 48 %. Les arguments qu'il développe brièvement à ce sujet pour revendiquer le versement d'une rente entière sont en tout cas dénués de pertinence, voire contradictoires avec les moyens qu'il invoque ensuite dans son mémoire où il réclame trois-quarts de rente ou une demi-rente.
Les modalités du paiement du quart de rente n'ont pas encore été arrêtées. Toutefois, ainsi que cela ressort explicitement de la décision du 4 avril 2008, celles-ci feront l'objet d'une décision ultérieure qui tiendra compte de demandes de compensation, de sorte que le recourant pourra les contester à ce moment-là.
6. Le recourant, qui succombe, supportera les frais de la procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal valaisan, Cour des assurances sociales, à l'Office fédéral des assurances sociales et à la Caisse de compensation du canton du Valais.
Lucerne, le 17 juillet 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Meyer Berthoud