Faits: A. A.a Originaire du Cameroun, X._, né le *** 1979 (alias Y._, né le *** 1987) a déposé une demande d'asile en Suisse le 8 novembre 2006, qui a été définitivement rejetée le 12 mars 2007, un délai lui étant imparti au 13 avril 2007 pour quitter la Suisse. Le 24 août 2011, il est devenu père de jumeaux et sa reconnaissance de paternité a été inscrite dans les registres de l'état civil. A.b Entre 2007 et 2011, X._ a fait l'objet en Suisse des condamnations pénales suivantes : - le 27 mars 2007, à cinq jours-amende de 480 fr. pour infraction à la LStup; - le 11 juin 2009, à quarante jours-amende pour faux dans les certificats, contravention à la législation sur le séjour et l'établissement des étrangers, séjour illégal, activité lucrative sans autorisation et contravention à la LStup; - le 23 février 2010, à 24 mois de privation de liberté assortie d'un sursis partiel et d'une amende de 500 fr. pour faux dans les certificats, blanchiment d'argent, infraction grave et contravention à la LStup ainsi que séjour illégal; - le 16 septembre 2011, à 20 jours de privation de liberté pour séjour illégal. A.c Parallèlement à ces condamnations, X._ a été le destinataire de différentes décisions et démarches de la part des autorités administratives : - le 24 avril 2007, le Service de la population du canton de Vaud (ci-après: le Service cantonal) lui a réservé un vol de départ prévu le 15 mai 2007; l'intéressé a refusé de signer le plan de vol, ne s'est pas présenté à l'aéroport et n'a plus donné signe de vie; - arrêté le 16 août 2007, X._ a été placé en détention administrative jusqu'au 12 octobre 2007; - le 3 mars 2010, X._ a été refoulé par vol spécial à destination du Cameroun, mais il est revenu en Suisse quelques jours plus tard; - le 18 janvier 2011, il a fait l'objet d'une décision d'interdiction d'entrée en Suisse pour une durée indéterminée; - le 21 mars 2011, le Service cantonal, faisant suite à une requête de l'intéressé alléguant des projets de mariage, a déclaré que son séjour n'était pas légal; - le 20 mai 2011, le Service cantonal a prononcé le renvoi de Suisse de X._, lui fixant un délai de départ au 19 juin 2011; - le 13 janvier 2012, le Service cantonal a refusé de lui délivrer une autorisation de séjour en raison notamment de ses condamnations pénales et a prononcé son renvoi de Suisse. B. Entre le 13 octobre 2011 et le 16 février 2012, X._ a été placé en détention administrative pour une durée de 6 mois, durant laquelle il a signé, le 4 novembre 2011, une déclaration de retour volontaire au Cameroun. Le 16 février 2012, la détention administrative de l'intéressé a été levée par le Service cantonal, pour qu'il puisse purger une peine de détention pénale jusqu'au 7 mars 2012. Le 6 mars 2012, un jour avant que X._ finisse de purger sa peine privative de liberté, le Service cantonal a requis du Juge de paix le placement en détention administrative de l'intéressé, afin de préparer son retour dans son pays d'origine. Par ordonnance du Juge de paix du 7 mars 2012, X._ a été placé en détention administrative. Ce magistrat a transmis le dossier à la Présidente du Tribunal cantonal pour qu'elle désigne un avocat d'office à l'intéressé. A la suite d'une requête de l'Office fédéral des migrations (ci-après: l'Office fédéral) du 13 mars 2012, l'Ambassade du Cameroun a fixé une audition de l'intéressé au 18 avril 2012. Le recours formé par X._ à l'encontre de l'ordonnance du 7 mars 2012 a été rejeté et la décision attaquée confirmée par arrêt du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal) du 17 avril 2012. C. A l'encontre de l'arrêt du Tribunal cantonal du 17 avril 2012, X._ forme un recours en matière de droit public au Tribunal fédéral. Il conclut principalement à la réforme de l'arrêt attaqué, à l'admission de son recours, à ce que l'ordonnance de mise en détention du 7 mars 2012 soit déclarée nulle, respectivement annulée et à ce qu'il soit immédiatement libéré. Subsidiairement, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause au Tribunal cantonal pour instruction complémentaire et nouvelle décision dans le sens des considérants. Il requiert par ailleurs l'assistance judiciaire. Par ordonnance présidentielle du 29 mai 2012, le Tribunal fédéral a rejeté la requête de mise en liberté immédiate formée à titre provisionnel par X._. Le Service cantonal a produit son dossier, mais il a renoncé à se déterminer, à l'instar du Tribunal cantonal. L'Office fédéral n'a pas pris position. X._ a déclaré s'en remettre à son mémoire de recours, tout en soulignant qu'aucune démarche en vue de l'exécution du renvoi n'avait été entreprise depuis deux mois. 