Faits:
A. Ressortissant camerounais né en 1979, X._ a déposé une demande d'asile en Suisse, qui a été rejetée le 10 juillet 2003 par l'Office fédéral des réfugiés, actuellement l'Office fédéral des migrations, (ci-après: l'Office fédéral). Le 17 septembre 2003, cette décision étant devenue définitive et exécutoire, l'intéressé s'est vu impartir un délai échéant le 10 novembre 2003 pour quitter la Suisse.
Le 25 octobre 2006, les autorités camerounaises ont établi un laissez-passer en faveur de X._, qui était dépourvu de documents d'identité. Ce laissez-passer est arrivé à échéance le 24 janvier 2007.
Le 16 novembre 2006, l'intéressé a refusé de signer un plan de vol à destination de son pays d'origine pour le 4 décembre 2006; il ne s'est pas présenté à cette date à l'aéroport et a disparu.
Le 23 janvier 2009, X._ a été interpellé en possession de documents d'identité volés et mis en détention préventive par le Juge d'instruction de l'arrondissement de Lausanne (ci-après: le Juge d'instruction).
Dans une décision du 30 janvier 2009, le Juge d'instruction a indiqué avoir ordonné la relaxation de X._ pour le 3 février 2009, "en mains de l'inspecteur de la police de sûreté (BRES)", pour que l'intéressé puisse être présenté au Juge de paix en vue de son éventuel placement en détention administrative. Il a ainsi déclaré sans objet la demande de mise en liberté formée par X._.
B. Le 2 février 2009, le Service de la population du canton de Vaud (ci-après: le Service de la population) a requis de la Police cantonale vaudoise l'arrestation de X._ et sa mise à disposition du Juge de paix des districts de Lausanne et de l'Ouest lausannois (ci-après: le Juge de paix) pour une audition prévue le 3 février 2009. Ce jour-là, le Service de la population a demandé au Juge de paix de placer X._ en détention administrative, afin de préparer son retour dans son pays d'origine.
A l'issue d'une audience tenue le 3 février 2009, le Juge de paix a ordonné la détention de X._ dès le 3 février 2009. L'ordonnance motivée a été notifiée le 4 février 2009.
C. Par arrêt du 13 mars 2009, la Chambre des recours du Tribunal cantonal vaudois (ci-après: le Tribunal cantonal) a rejeté le recours de X._ contre l'ordonnance du 3 février 2009 et confirmé la décision attaquée.
D. Le 23 mars 2009, X._ a déposé au Tribunal fédéral un recours en matière de droit public contre l'arrêt du Tribunal cantonal du 13 mars 2009. Il conclut, sous suite de frais et dépens, principalement, à la réforme de l'arrêt attaqué en ce sens que son recours cantonal soit admis, que l'ordonnance du Juge de paix du 3 février 2009 soit annulée et qu'il soit immédiatement libéré; subsidiairement, il conclut à l'annulation de l'arrêt entrepris et au renvoi de la cause au Tribunal cantonal pour nouvelle instruction et nouvelle décision dans le sens des considérants. Il requiert en outre la production de deux dossiers et sollicite l'assistance judiciaire.
Le Tribunal cantonal se réfère à l'arrêt attaqué. Le Juge de paix a renoncé à répondre au recours et l'Office fédéral n'a pas présenté d'observations.
Le Service de la population a déposé ses déterminations tardivement, à l'instar du recourant.
E. Par ordonnance du 27 mars 2009, le Président de la IIe Cour de droit public a rejeté la requête de mesures provisionnelles tendant à la libération immédiate du recourant.

Considérant en droit:
1. 1.1 L'étranger placé en détention en vue du renvoi ou de l'expulsion au sens de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) a qualité pour déposer un recours en matière de droit public au Tribunal fédéral contre la décision confirmant sa détention rendue en dernière instance cantonale (cf. <ref-law>). Interjeté dans le délai et la forme prévus par la loi (cf. art. 42 et 100 al. 1 LTF), le présent recours est donc en principe recevable.
1.2 Les déterminations du Service de la population et les observations du recourant à leur sujet, déposées hors délai, sont irrecevables. Il en va de même des pièces produites à l'appui du recours, qui contreviennent à l'<ref-law>.
1.3 Le recourant requiert la production des dossiers le concernant par le Service de la population et par le Juge d'instruction. Le Service de la population a produit son dossier, comme d'ailleurs le Tribunal cantonal et le Juge de paix. Quant au dossier du Juge d'instruction, il s'agit d'une preuve nouvelle qui ne résulte pas de la décision de l'autorité précédente, de sorte que la requête est irrecevable (<ref-law>). Au demeurant, ce dossier est sans pertinence (cf. infra consid. 2).
2. Le litige porte exclusivement sur la mise en détention du recourant en application de l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. En conséquence, seule la détention administrative et le respect de la procédure de la part des autorités en relation avec cette mesure peuvent être revues.
L'Autorité de céans n'entrera donc pas en matière sur les griefs du recourant à l'encontre de son maintien en détention préventive jusqu'au 3 février 2009 par le Juge d'instruction, dont il a été informé le 30 janvier 2009. Il convient toutefois de souligner que ce magistrat n'a aucune compétence s'agissant de la détention administrative relevant de la LEtr (sur les risques liés à une telle compétence, cf. <ref-ruling> consid. 3c p. 58), de sorte qu'il ne pouvait valablement requérir, le 30 janvier 2009, de la police qu'elle retienne le recourant pour l'amener auprès du Juge de paix en vue de son éventuelle détention administrative. Cette compétence ressortit exclusivement au Service de la population (cf. art. 15 al. 1 de la loi du 18 décembre 2007 d'application dans le canton de Vaud de la législation fédérale sur les étrangers; LVLEtr; RSV 142.11). Dès lors que, selon les constatations cantonales, le Service de la population a formulé une telle requête le 2 février 2009 (cf. infra consid. 5.1), la déclaration du Juge d'instruction tendant à ce que la police retienne le recourant pour le présenter au Juge de paix n'a pas joué de rôle. Partant, bien qu'indue, cette intervention ne permet pas de conclure à l'illicéité de la mise en détention administrative du recourant.
3. 3.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement le respect du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'<ref-law>, selon lequel le Tribunal fédéral n'examine la violation de droits fondamentaux ainsi que celle de dispositions de droit cantonal et intercantonal que si ce grief a été invoqué et motivé par le recourant de manière suffisante (<ref-ruling> consid. 2.3 p. 466). L'acte de recours doit alors, sous peine d'irrecevabilité, contenir un exposé succinct des droits ou principes constitutionnels violés et préciser en quoi consiste la violation (<ref-ruling> consid. 1.4.2 p. 254).
3.2 Sauf dans les cas cités expressément à l'<ref-law>, le recours ne peut pas être formé pour violation du droit cantonal en tant que tel. En revanche, le recourant peut faire valoir que la mauvaise application du droit cantonal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à d'autres droits constitutionnels (<ref-ruling> consid. 2.3 p. 466). Ce faisant, il doit respecter les exigences de motivation de l'<ref-law>.
4. 4.1 La détention du recourant repose sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr, qui prévoit que, lorsqu'une décision de renvoi ou d'expulsion de première instance a été notifiée, l'autorité compétente peut, afin d'en assurer l'exécution, mettre la personne concernée en détention si des éléments concrets font craindre qu'elle entende se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer (ch. 3) ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités (ch. 4). Ces deux chiffres décrivent des comportements permettant de conclure à l'existence d'un risque de fuite ou de disparition (Untertauchensgefahr); ils peuvent donc être envisagés ensemble (Andreas Zünd, Kommentar Migrationsrecht, 2008, n° 6 ad art. 76 LEtr). Selon la jurisprudence, un risque de fuite existe notamment lorsque l'étranger a déjà disparu une première fois dans la clandestinité, qu'il tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore lorsqu'il laisse clairement apparaître qu'il n'est pas disposé à retourner dans son pays d'origine (<ref-ruling> consid. 3.1 p. 58 s; arrêt 2C_128/2009 du 30 mars 2009 consid. 3.1).
4.2 Le 10 juillet 2003, l'Office fédéral a rejeté la demande d'asile de X._. Une fois cette décision définitive et exécutoire, un délai échéant le 10 novembre 2003 a été imparti à l'intéressé pour quitter la Suisse. Celui-ci n'a pas respecté ce délai, ni cherché à se procurer des papiers d'identité, bien qu'il en fût dépourvu. Le Service de la population a dû faire des démarches pour obtenir un laissez-passer des autorités camerounaises. De plus, le recourant a refusé de signer, le 16 novembre 2006, un plan de vol à destination de son pays d'origine et ne s'est pas présenté à l'aéroport le 4 décembre 2006, date prévue pour son départ, mais est entré dans la clandestinité. Le 23 janvier 2009, il a été interpellé en possession de documents d'identité volés; il détenait aussi deux abonnements des CFF établis sous un nom d'emprunt mais avec sa photographie. Il existe ainsi des indices sérieux et concrets permettant de conclure que l'intéressé a l'intention de se soustraire à son renvoi. Sa mise en détention respecte donc l'art. 76 al. 1 let. b ch. 3 et 4 LEtr.
4.3 La thèse du recourant, qui conteste que sa détention administrative puisse reposer sur la décision de l'Office fédéral du 10 juillet 2003, car il aurait quitté la Suisse en février 2007, ne peut être suivie. En effet, la décision de renvoi du 10 juillet 2003 n'a jamais été exécutée, dès lors que le recourant n'a pas quitté la Suisse dans le délai qui lui a été imparti par les autorités ni n'a pu être renvoyé, les démarches entreprises en ce sens s'étant soldées par un échec, le recourant ayant refusé de signer le plan de vol à destination de son pays d'origine et ne s'étant pas présenté, le 16 novembre 2006, à l'aéroport. Depuis lors, le recourant a disparu dans la clandestinité. Il prétend certes qu'il aurait finalement quitté la Suisse en février 2007. Cet élément a seulement été évoqué comme une possibilité, mais sans être tenu pour établi dans l'arrêt attaqué. Dès lors que le recourant ne se plaint pas de ce que les faits auraient été constatés de façon manifestement inexacte ou arbitrairement sur ce point (cf. <ref-law>), il n'est pas possible d'en tenir compte. On ne peut donc admettre que la décision de renvoi du 10 juillet 2003 aurait été exécutée, de sorte que cette dernière n'ayant été ni révoquée ni annulée, elle reste opposable au recourant (cf. arrêt 2A.305/2001 du 18 juillet 2001 consid. 3d). Lorsqu'il a été placé en détention administrative au début février 2009, le recourant faisait donc bien l'objet d'une décision de renvoi au sens de l'art. 76 al. 1 LEtr. La détention n'est donc pas, sous cet angle, illégale, de sorte que l'on ne voit pas qu'elle puisse être contraire aux art. 31 al. 1 Cst. ou 5 par. 1 CEDH, également invoqués par le recourant à l'appui de ce grief.
4.4 Le recourant reproche au Tribunal cantonal d'avoir violé l'art. 80 al. 4 LEtr et le principe de la proportionnalité, en ne tenant pas compte de sa situation familiale. Il allègue être le père de deux filles mineures, orphelines de mère, avec lesquelles il vivrait en Espagne et qu'il n'aurait confiées à un tiers que pour un bref voyage en Suisse. Son absence prolongée mettrait ses enfants en danger et aucune démarche n'aurait été entreprise pour qu'il puisse rejoindre ses enfants.
Selon l'art. 80 al. 4 LEtr, lorsqu'elle examine la décision de détention, l'autorité judiciaire tient compte de la situation familiale de la personne détenue. Comme le relève à juste titre le Tribunal cantonal, cette disposition ne peut servir à remettre en cause le renvoi lui-même, mais seulement à faire obstacle à la détention. Or, l'étranger qui est renvoyé ne peut choisir le pays où il veut aller que s'il a la possibilité de s'y rendre légalement (art. 69 al. 2 LEtr) et le recourant ne prouve pas qu'il soit autorisé à entrer (et à séjourner) en Espagne. Dans ces circonstances, l'argument selon lequel le recourant doit s'occuper de ses deux filles mineures demeurées en Espagne n'est pas propre à faire apparaître comme illégal ou contraire à la proportionnalité l'arrêt attaqué confirmant sa détention administrative.
4.5 Enfin, l'exécution du renvoi ne s'avère pas d'emblée impossible pour des raisons juridiques ou matérielles (cf. art. 80 al. 6 let. a LEtr a contrario) et devrait avoir lieu dans un délai raisonnable, puisque l'arrêt attaqué retient que des démarches ont été entreprises pour l'obtention d'un laissez-passer permettant le retour du recourant dans sa patrie (cf. art. 76 al. 4 LEtr).
La détention administrative du recourant n'apparaît donc pas, en tant que telle, contraire au droit fédéral.
5. Encore faut-il se demander si la procédure suivie par les autorités vaudoises pour aboutir à la mise en détention litigieuse respecte les exigences légales, ce qui est contesté dans le recours.
5.1 Le recourant soutient que l'art. 16 al. 1 LVLEtr aurait été gravement violé en raison du non-respect des délais prévus. On peut se demander si un tel moyen, tiré apparemment de l'arbitraire, est suffisamment motivé s'agissant de l'application du droit cantonal (cf. supra consid. 3.2). La question peut cependant rester ouverte car le délai de 96 heures est également prescrit par l'art. 80 al. 2 LEtr et le Tribunal doit en vérifier d'office le respect (<ref-law>).
5.1.1 Selon l'art. 80 LEtr, la détention est ordonnée par l'autorité du canton qui exécute le renvoi ou l'expulsion (al. 1). L'al. 2 1ère phrase de cette disposition prévoit que la légalité et l'adéquation de la détention doivent être examinées dans un délai de 96 heures par une autorité judiciaire au terme d'une procédure orale. L'autorité compétente pour exécuter le renvoi est, dans le canton de Vaud, le Service de la population (cf. art. 3 LVLEtr), alors que le contrôle judiciaire est du ressort du "juge de paix du district de Lausanne" (cf. art. 11 et 15 LVLEtr). Selon l'art. 16 al. 1 LVLEtr, la personne retenue doit être entendue par le Juge de paix dans les 24 heures. Le Juge de paix statue lors de l'audition et rend, le cas échéant, un ordre de mise en détention. Il notifie sa décision motivée par écrit dans les 96 heures. Ces délais se calculent à partir du moment où l'intéressé a effectivement été détenu pour des motifs de droit des étrangers. Si la détention administrative se recoupe avec une détention de nature pénale, le moment auquel le détenu est libéré sur le plan pénal est déterminant pour calculer le début de la détention administrative (<ref-ruling> consid. 2b/aa p. 175 s.; arrêt 2A.455/1996 du 4 octobre 1996 consid. 1b).
5.1.2 Le recourant fonde son raisonnement sur la prémisse erronée que, depuis le moment où le Juge d'instruction a ordonné sa relaxation, soit le 28 janvier 2009 (subsidiairement le 30), son maintien en détention préventive n'avait que pour but de le présenter au Juge de paix. Les délais de l'art. 16 al. 1 LVLEtr devaient ainsi courir depuis le 28 ou le 30 janvier 2009. Ce faisant, il perd de vue que le Juge d'instruction a certes annoncé à fin janvier que le recourant serait relaxé, mais seulement à partir du 3 février 2009. Jusqu'à cette date, le recourant demeurait donc détenu à titre préventif sous l'angle du droit pénal. Comme déjà indiqué, le point de savoir si le Juge d'instruction était en droit de prolonger la détention préventive jusqu'au 3 février 2009 relève de la procédure pénale et ne peut être revu dans la présente procédure (cf. supra consid. 2). Au demeurant, le Juge d'instruction n'avait pas la compétence de prononcer la détention administrative du recourant (cf. art. 17 LVLEtr).
5.1.3 La détention administrative du recourant trouve son origine dans la réquisition du 2 février 2009 émanant du Service de la population, soit de l'autorité compétente en la matière, qui demandait à la police de retenir l'intéressé et de le mettre à disposition du Juge de paix. Le Juge d'instruction ayant libéré le recourant, jusqu'alors détenu préventivement, à partir du 3 février 2009, la détention n'a pu revêtir un caractère administratif avant cette date. Or, le 3 février 2009, le recourant a été entendu par le Juge de paix, qui a ordonné sa mise en détention administrative immédiate; il a notifié cette décision par écrit le 4 février 2009. En considérant que les délais de 24 et de 96 heures prévus par la loi avaient été respectés, le Tribunal cantonal n'a ainsi nullement méconnu gravement l'art. 16 al. 1 LVLEtr ni violé l'art. 80 al. 2 LEtr. La détention n'étant pas illégale de ce point de vue, elle ne saurait être contraire aux art. 31 al. 1 et 5 par 1 CEDH, également invoqués par le recourant dans ce contexte.
5.2 Toujours en relation avec la procédure, le recourant se plaint encore d'une violation de l'interdiction de l'arbitraire (art. 9 Cst. et 11 Cst./VD) et des garanties de procédure judiciaire (art. 30 al. 1 Cst., 27 al. 1 Cst./VD et 31 al. 1 et 2 LVLEtr), pour le cas où les juges cantonaux se seraient prononcés sans être en possession des dossiers du Service de la population et du Juge d'instruction. Il demande que, si tel était le cas (ce qu'il ignore), le vice soit réparé en application de l'<ref-law> ou la cause renvoyée au Tribunal cantonal.
5.2.1 Dans la mesure où le recourant n'indique pas en quoi les dispositions de nature constitutionnelle dont il se prévaut auraient été violées, son grief n'est pas recevable. Celui-ci ne sera examiné que dans la mesure où il porte sur une application arbitraire de l'art. 31 LVLEtr.
5.2.2 Comme déjà indiqué, la détention préventive prononcée par le Juge d'instruction sur le plan pénal ne fait pas l'objet de la présente procédure. Partant, on ne saurait reprocher au Tribunal cantonal d'avoir appliqué arbitrairement le droit cantonal en statuant sans être en possession de l'ensemble du dossier pénal.
5.2.3 Reste le dossier du Service de la population. L'art. 31 LVLEtr prévoit que le Tribunal cantonal revoit librement la décision de première instance (al. 1). Il établit les faits d'office et peut ordonner à cet effet toutes les mesures d'instruction qu'il juge utile (al. 2). Contrairement à ce que soutient le recourant, cette disposition, examinée sous l'angle de l'arbitraire, n'impose pas au Tribunal cantonal, chargé de se prononcer sur la légalité d'une mesure de détention ordonnée par le Juge de paix, de requérir d'emblée le dossier du Service de la population. L'art. 81 al. 2 de la loi vaudoise du 28 octobre 2008 sur la procédure administrative (RSV 173.36), également invoqué par le recourant, ne l'exige pas non plus : il prévoit seulement que l'autorité intimée remet son dossier, en principe avec ses déterminations. Or, l'autorité intimée est ici le Juge de paix et non le Service de la population.
Ce n'est que si les juges cantonaux avaient renoncé à une mesure d'instruction utile, violant leur obligation d'établir les faits d'office, que l'on pourrait admettre une application arbitraire de l'art. 31 LVLEtr. En l'espèce, rien n'indique que les juges cantonaux n'auraient pas été en possession du dossier du Juge de paix lorsqu'ils ont statué, ce que le recourant ne prétend pas du reste. Il soutient seulement que ce dossier serait trop "maigre" pour que les juges cantonaux puissent se dispenser de requérir le dossier du Service de la population. Cette position ne peut être suivie. Le Juge de paix statue en effet, en vertu de l'art. 21 al. 1 LVLEtr, sur la base d'une requête motivée, précise et complète, ainsi que des pièces remises, après avoir entendu la personne concernée. Son dossier comporte par définition ces éléments, de sorte que le Tribunal cantonal ne peut se voir reprocher de violer de manière générale son obligation d'établir les faits d'office s'il estime, sur la base du dossier du Juge de paix, disposer des éléments utiles pour statuer, sans requérir au surplus le dossier du Service de la population. Le recourant ne fait du reste état d'aucun élément concret déterminant qui aurait été omis dans l'arrêt attaqué. Il se prévaut uniquement de la pièce 4, qu'il produit et qui consiste dans son procès-verbal d'arrestation du 23 janvier 2009. On ne voit pas qu'un tel document soit pertinent en l'espèce, ce que le recourant n'explique pas du reste, de sorte qu'il ne saurait apparaître comme utile au sens de l'art. 31 al. 2 LVLEtr.
Le grief est en conséquence infondé, dans la mesure où il est recevable.
6. Ni l'arrêt attaqué ni la décision du Juge de paix qu'il confirme ne mentionnent la durée de la détention prévue. L'absence d'indication quant à la durée de la détention ne suffit pas à qualifier celle-ci d'inadmissible (arrêt 2C_575/2008 du 1er septembre 2008 consid. 5.3). Il n'en demeure pas moins que la détention du recourant doit respecter les délais légaux. Selon l'art. 76 al. 3 LEtr, la durée de la détention prononcée, comme en l'espèce, en vertu de l'al. 1 let. b ch. 3 et 4 de cet article, ne peut excéder trois mois; si des obstacles particuliers s'opposent à l'exécution du renvoi ou de l'expulsion elle peut, avec l'accord de l'autorité judiciaire cantonale, être prolongée de quinze mois au plus (art. 76 al. 3 LEtr). Le délai fixé en mois se calcule de quantième en quantième, par référence à l'<ref-law>, à partir du moment où l'étranger est détenu à titre administratif (cf. <ref-ruling> consid. 2b/bb p. 176; ZÜND, op. cit., n° 8 ad art. 76 LEtr). Comme indiqué, la détention administrative du recourant ayant débuté le 3 février 2009, elle peut durer au maximum trois mois, soit jusqu'au 2 mai 2009, sous réserve d'une prolongation remplissant les conditions de l'art. 76 al. 3 LEtr.
7. Compte tenu de ce qui précède, aucun motif de nature matérielle ou procédurale ne justifie la réforme ou l'annulation de l'arrêt attaqué. Le recours sera donc rejeté, dans la mesure où il est recevable.
L'intéressé a demandé l'assistance judiciaire. On peut admettre, sur la base du dossier, qu'il ne dispose pas de ressources suffisantes; en outre, les questions à résoudre démontrent que le recours n'était pas dépourvu de chances de succès, au sens où l'entend la jurisprudence (cf. <ref-ruling> consid. 5 p. 616), de sorte qu'il convient d'octroyer l'assistance judiciaire.
En conséquence, il ne sera pas perçu de frais judiciaires. Me Luc Recordon sera désigné à titre d'avocat d'office du recourant et une indemnité appropriée lui sera versée par la Caisse du Tribunal fédéral (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est admise.
3. Il n'est pas perçu de frais judiciaires.
4. Me Luc Recordon, avocat, est désigné comme avocat d'office du recourant et une indemnité de 1'500 fr. lui sera versée à titre d'honoraires par la Caisse du Tribunal fédéral.
5. Le présent arrêt est communiqué au mandataire du recourant, au Juge de paix des districts de Lausanne et de l'Ouest lausannois, au Service de la population et à la Chambre des recours du Tribunal cantonal du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 29 avril 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Dupraz