Faits:
A. Le 20 août 2008, X._, ressortissant kosovar né en 1975, domicilié à Podujevo (Kosovo), a déposé une demande de visa auprès de l'Ambassade de Suisse de Pristina en vue d'obtenir une autorisation d'entrée dans notre pays pour se marier avec Y._, une ressortissante suisse née en 1958 et domiciliée à Z._ (Valais).
Les fiancés ont été entendus chacun de leur côté, le premier dans les locaux de la représentation suisse au Kosovo, le 28 juillet 2009, la seconde par la Police communale de sa commune de domicile, le 24 juin 2009. Des questions leur ont été posées en vue de vérifier la réalité de leur relation et la sincérité de leur intention matrimoniale. Il en est notamment ressorti que les intéressés s'étaient rencontrés en 2006 à Rome, qu'ils avaient ensuite vécu entre 2007 et 2008 pendant plusieurs mois ensemble à Z._ dans la maison de Y._ avant le dépôt par le fiancé, en août 2008, de la demande litigieuse pour venir se marier en Suisse.
Par décision du 27 octobre 2009, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a rejeté "la demande d'autorisation d'entrée et de séjour déposée par X._". Il a estimé que le mariage envisagé était de complaisance au vu notamment de la différence d'âge entre les fiancés et de leurs déclarations contradictoires ou erronées sur certains points, comme la date de leur rencontre à Rome, leur(s) période(s) de vie commune à Z._ ou la profession exercée par l'autre.
Saisi d'un recours contre la décision précitée, le Conseil d'Etat valaisan (ci-après: le Conseil d'Etat) l'a rejeté le 24 novembre 2010.
B. X._ a recouru contre la décision du Conseil d'Etat, en contestant la pertinence des indices retenus par cette autorité pour conclure au caractère de complaisance du mariage projeté.
Par arrêt du 25 mars 2011, le Tribunal cantonal du canton du Valais, Cour de droit public (ci-après: le Tribunal cantonal) a rejeté le recours. En bref, il a certes retenu un certain nombre de points accréditant la thèse d'un véritable projet de mariage entre les fiancés, mais a néanmoins estimé que, "dans la balance", les indices parlant en faveur d'un mariage de complaisance l'emportaient. Il ressort également de cet arrêt que, peu avant que les juges ne statuent sur son recours, X._, revenu clandestinement en Suisse, a été interpellé par un inspecteur du travail le 2 mars 2011 sur un chantier à A._; son cas a été dénoncé au Service cantonal, qui a ordonné son placement immédiat en détention en vue de son refoulement (décision confirmée par le Juge unique le 4 mars suivant); le même jour, soit le 2 mars 2011, l'Office fédéral des migrations (ODM) a prononcé à son encontre une interdiction d'entrée en Suisse valable jusqu'au 1er mars 2013.
C. Dans une écriture intitulée "recours en matière de droit public et recours constitutionnel subsidiaire", X._ demande au Tribunal fédéral de réformer l'arrêt précité du Tribunal cantonal du 25 mars 2011, en ce sens qu'une autorisation d'entrée et de séjour lui soit octroyée. Subsidiairement, il conclut à l'annulation de cet arrêt et au renvoi de la cause à l'autorité cantonale pour nouvelle décision dans le sens des considérants, le tout sous suite de frais et dépens. Il fonde son droit à une autorisation de séjour sur le cas d'extrême gravité prévu par le droit interne et sur la protection de la vie privée et familiale garantie à l'art. 8 CEDH. En substance, il réfute la pertinence des indices retenus par le Tribunal cantonal pour admettre un mariage de complaisance et insiste sur les indices contraires attestant la réalité des liens avec sa fiancée et la sincérité de leur projet de matrimonial.
Le Tribunal cantonal renonce à déposer des observations sur le recours, tandis que Conseil d'Etat conclut à son rejet, sous suite de frais et dépens. L'Office fédéral des migration (ODM) préavise également en faveur du rejet du recours.
Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF). Il contrôle donc librement la recevabilité des recours déposés devant lui.
1.1 Le recourant a déposé depuis son pays une demande de visa pour la Suisse en vue de se marier avec Y._, en précisant qu'il comptait vivre en Suisse avec son épouse après le mariage (à la question "durée prévue du séjour", il a répondu: "forever"). Comme un tel projet implique un séjour plus long que trois mois, le visa ne peut être octroyé que si le requérant sollicite avant son entrée en Suisse une "autorisation" auprès de l'autorité compétente du lieu de résidence envisagé (cf. art. 10 al. 2 LEtr). C'est dans ce cadre que le Service cantonal a été saisi de la cause et qu'il a rejeté, selon ses termes, "la demande d'entrée et d'autorisation de séjour en Suisse présentée par X._". Cette décision, confirmée par l'arrêt attaqué, constitue l'objet de la contestation.
1.2 Selon l'art. 83 let. c LTF, le recours en matière de droit public est irrecevable à l'encontre des décisions en matière de droit des étrangers qui concernent l'entrée en Suisse (ch. 1) ou une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit (ch. 2) ou encore des dérogations aux conditions d'admission (ch. 5).
1.2.1 En tant que le recourant demande l'octroi d'une autorisation d'entrée, sa conclusion n'est pas recevable en vertu de l'art. 83 let. c ch. 1 LTF. Du reste, la décision attaquée ne tranche pas - du moins pas directement - le droit du recourant d'entrer en Suisse; la compétence du Service cantonal se limite en effet, s'il accepte la demande d'autorisation de séjour, à "autoriser" la représentation suisse à délivrer un visa (cf. art. 5 de l'Ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative; OASA, RS 142.201), document sans lequel l'entrée en Suisse du recourant n'est pas possible en l'absence d'accord de notre pays avec le Kosovo (cf. art. 5 a contrario de l'ordonnance du 22 octobre 2008 sur l'entrée et l'octroi de visas; OEV, RS 142.204).
1.2.2 Le recourant ne peut donc s'en prendre à la décision attaquée que dans la mesure où celle-ci lui refuse l'octroi d'une autorisation de séjour. C'est toutefois seulement s'il peut déduire du droit fédéral ou du droit international un droit à une autorisation de séjour qu'il peut, d'après l'art. 83 let. c ch. 2 LTF, agir par la voie du recours en matière de droit public. A cet égard, il suffit qu'il démontre de manière soutenable l'existence d'un droit potentiel à une telle autorisation pour que le recours soit recevable; le point de savoir si toutes les conditions sont effectivement réunies dans un cas particulier relève de l'examen au fond (ATF 136 II 177 consid. 1.1 p. 179).
Contrairement à ce qu'il prétend, le recourant ne peut pas exciper un droit à une autorisation de séjour de l'art. 30 al. 1 let. b LEtr (cas d'extrême gravité permettant de déroger aux conditions d'admission) en raison de la nature potestative ("Kann-Vorschrift") de cette disposition, comme le confirment les directives "Domaine des étrangers" de l'ODM (ch. 5.6.2.2.3) que les autorités cantonales ont prises en compte dans leur appréciation; selon celles-ci, "en application de l'art. 30 let. b LEtr en lien avec l'art. 31 OASA, une autorisation de séjour de courte durée peut en principe (c'est le Tribunal fédéral qui souligne) être délivrée pour permettre à un étranger de préparer en Suisse son mariage avec un citoyen suisse...". Faute de véritable droit à une autorisation de séjour, le recours est dès lors irrecevable en vertu de l'art. 83 let. c ch. 2 LTF en tant qu'il est fondé sur l'art. 30 al. 1 let. b LEtr. De plus, si on la considère sous l'angle de cette dernière disposition, soit comme un refus de déroger aux conditions d'admission, la décision attaquée ne pourrait de toute façon pas faire l'objet d'un recours en matière de droit public en vertu de l'art. 83 let. c ch. 5 LTF (cf. arrêt 2C_75/2011 du 6 avril 2011 consid. 1.1.1).
1.2.3 Le recourant fonde également son argumentation sur le droit au respect de la vie privée et familiale garanti à l'art. 8 § 1 CEDH. Selon la jurisprudence, cette disposition permet en principe à un célibataire étranger de déduire un droit à une autorisation de séjour - de courte durée - en présence d'indices concrets d'un mariage sérieusement voulu et imminent avec une personne ayant le droit de résider durablement en Suisse (cf. arrêts 2C_97/2010 du 4 novembre 2010 consid. 3.1; 2C_25/2010 du 2 novembre 2010 consid. 6.1 et les références citées). Dès lors que le recourant conteste avec vraisemblance la pertinence des motifs retenus par les premiers juges pour qualifier de fictif son projet de mariage, il faut admettre qu'il étaye l'existence d'un droit potentiel à une autorisation de séjour de manière suffisante pour échapper à la clause d'irrecevabilité prévue à l'art. 83 let. c ch. 2 LTF; le point de savoir si le projet de mariage revêt, ou non, un caractère de complaisance, relève du fond du litige.
1.2.4 Par ailleurs, dans la mesure où le recours remplit, comme en l'espèce, les conditions de recevabilité requises sous l'angle de l'art. 8 par. 1 CEDH, la décision attaquée, bien qu'elle emporte un refus de déroger aux conditions d'admission, peut faire l'objet d'un recours en matière de droit public nonobstant la clause d'exclusion de l'art. 83 let. c ch. 5 LTF en ce domaine. Conformément à la réserve de l'art. 3 al. 2 LEtr en faveur des engagements internationaux de la Suisse, le recourant peut en effet inférer de l'art. 8 par. 1 CEDH, s'il en réunit les conditions, un véritable droit d'être admis en Suisse, indépendamment des conditions d'admission laissées à l'appréciation des autorités de police des étrangers aux art. 18 à 29 LEtr (cf. arrêt 2C_75/2011 du 6 avril 2011 consid. 1.1.1).
1.3 Pour le surplus, le recours est dirigé contre une décision finale (art. 90 LTF) rendue dans une cause de droit public (art. 82 let. a LTF) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). En outre, il a été déposé en temps utile (art. 100 al. 1 LTF) et en la forme prévue (art. 42 LTF) par les destinataires de la décision attaquée qui ont un intérêt digne de protection à l'annulation ou à la modification de celle-ci (art. 89 al. 1 LTF). Il est donc recevable comme recours en matière de droit public et, par voie de conséquence, irrecevable comme recours constitutionnel subsidiaire (cf. art. 113 LTF).
2. 2.1 Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral, qui comprend les droits de nature constitutionnelle (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF (sur ces exigences, cf. ATF 136 II 304 consid. 2.5 p. 314; 136 I 229 consid. 4.1 p. 235; 133 II 249 consid. 1.4 p. 254 et les arrêts cités). Il y procède en se fondant sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF), à moins que ceux-ci n'aient été établis de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF).
2.2 A l'appui de ses observations du 14 octobre 2011, le recourant a produit de nouvelles pièces, notamment des réservations de vol concernant deux voyages de Y._ au Kosovo prévus en août et octobre 2011. Il s'agit de moyens de preuves nouveaux qui portent sur des faits postérieurs à l'arrêt attaqué et qui, comme tels, sont irrecevables (cf. art. 99 al. 1 LTF).
3. 3.1 Comme l'a jugé le Tribunal cantonal, un étranger ne saurait déduire un droit à une autorisation de séjour de l'art. 8 par. 1 CEDH - ni d'ailleurs d'une disposition du droit interne (cf. art. 51 al. 1 let. a et al. 2 let. a LEtr) - en invoquant un mariage de complaisance; la Cour européenne des droits de l'homme (CourEDH) a récemment rappelé que les Etats membres pouvaient prendre des mesures pour contrer cette forme particulière d'abus de droit (arrêt du 14 décembre 2010 dans la cause O'Donoghue et consorts c./Royaume-Uni, requête no 34848/07, points 83 ss). A ce titre, le législateur suisse a adopté, au cours des dernières années, plusieurs dispositions du code civil pour prévenir les mariages de complaisance (cf. art. 97a, 98 al. 4, 99 al. 4 et 105 ch. 4 CC; cf. arrêt 5A_225/2011 du 9 août 2011 consid. 5.1.2 in fine). Un projet de mariage revêt ainsi un caractère de complaisance et permet à l'officier d'état civil de refuser de prêter son concours, selon l'art. 97a al. 1 CC, "lorsque l'un des fiancés ne veut manifestement pas fonder une communauté conjugale mais éluder les dispositions sur l'admission et le séjour des étrangers". Cette définition correspond à celle admise de longue date par la jurisprudence rendue en matière de droit des étrangers (cf. ATF 127 II 49 consid. 4a p. 55; 122 II 289 consid. 2 p. 294 ss; 121 II 5 consid. 3a p. 6, 97 consid. 3 p. 101 ss; arrêts 2C_811/2010 du 23 février 2011 consid. 4.4.1 et 2C_222/2008 du 31 octobre 2008 consid. 3.3 in fine et 4.3 et les références citées).
La volonté de fonder une communauté conjugale est un élément intime qui, par la nature des choses, ne peut guère être prouvé directement. Le plus souvent, l'abus ne pourra être établi qu'au moyen d'un faisceau d'indices, tels qu'une grande différence d'âge entre les fiancés, une impossibilité ou de grandes difficultés à communiquer entre eux, une méconnaissance réciproque de leur cadre de vie et de leurs conditions d'existence (famille, amis, profession, hobbies, habitudes, etc.), un arrangement financier en vue du mariage, un projet de mariage élaboré peu de temps après la rencontre des fiancés, une procédure de renvoi en cours contre le fiancé dont le droit de résider en Suisse dépend de la conclusion du mariage, une absence de vie commune des fiancés avant le mariage, l'appartenance de la personne admise à résider en Suisse à un groupe social marginal, etc. (cf. ATF 122 II 289 consid. 2b p. 295; 121 II 101 consid. 3b p. 101 s.; arrêt 5A_201/2011 du 26 juillet 2011 consid. 3.1.1; voir aussi la directive de l'ODM du 22 décembre 2005 intitulée "lutte contre les mariages de complaisance"). Les constatations portant sur des indices peuvent concerner des circonstances externes, tout comme des éléments d'ordre psychique, relevant de la volonté interne (des époux). Il s'agit, dans les deux cas, de constatations de fait (cf. ATF 128 II 145 consid. 2.3 p. 152 et les arrêts cités) qui lient le Tribunal fédéral, sauf si elles ont été établies de façon manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF (cf. supra consid. 2; arrêt précité 5A_201/2011 consid. 3.1.2).
Comme le prescrit désormais expressément l'art. 97a al. 1 CC, il faut que l'absence de volonté de fonder une communauté conjugale soit manifeste pour que l'officier d'état civil puisse refuser son concours au mariage. Il n'en va pas différemment pour la police des étrangers qui doit faire preuve de retenue dans son appréciation et n'admettre le caractère de complaisance d'un projet de mariage dans un cas particulier qu'en présence d'indices clairs et concrets en ce sens (cf. ATF 128 II 145 consid. 2.2 p. 151; 127 II 49 consid. 5a p. 57 et les arrêts cités); seul l'abus manifeste d'un droit doit être sanctionné (cf. ATF 121 II 97 consid. 4a p. 103; arrêt 2C_252/2009 du 4 décembre 2009 consid. 4). En outre, la preuve de l'abus doit être apportée par les autorités, sous réserve de l'obligation des parties de collaborer à l'établissement des faits (cf. arrêt 2A.715/2005 du 13 février 2006 consid. 2.4 et 2.7.1 et les références citées). En l'absence d'indices concrets suffisants, le projet matrimonial ne saurait être considéré comme ne reflétant pas la réelle volonté des fiancés. En cas de doute, il faut bien plutôt considérer que ceux-ci veulent fonder une véritable communauté conjugale (cf. arrêt 2C_587/2008 du 4 décembre 2008 consid. 4.1), quitte, par la suite, à ne pas renouveler ou à révoquer l'autorisation de séjour si le doute initial devait finalement se confirmer à la lumière du comportement subséquent des époux (cf. arrêts 2C_473/2008 du 17 novembre 2008 consid. 2.1 et 2C_750/2007 du 8 avril 2008 consid. 2.3).
3.2 Pour l'essentiel, le Tribunal cantonal a considéré, dans son appréciation, que les indices parlant en faveur d'un mariage fictif l'emportaient, dans "la balance", sur ceux établissant la volonté des fiancés de fonder une communauté conjugale; il a notamment inféré cette conclusion de la différence d'âge existant entre les fiancés (17 ans) et des contradictions et/ou erreurs émaillant leurs déclarations; sur ce dernier point, il a estimé "que la lecture des procès-verbaux d'audition figurant au dossier autorise à conclure sans arbitraire à l'existence de projets de mariage fictif" (arrêt attaqué, consid. 4a in fine).
Ce raisonnement trahit une mauvaise compréhension et application de la notion d'abus de droit, en particulier des règles posées en la matière par la jurisprudence pour qu'un mariage - respectivement un projet de mariage - puisse être qualifié de fictif. D'une part, la référence à la notion d'arbitraire est dénuée de pertinence dans un domaine où la juridiction cantonale jouit d'un plein pouvoir d'examen en fait et en droit. D'autre part, les premiers juges ne devaient pas, comme ils l'ont fait, procéder à une pesée, à une pondération ou à une mise en balance des différents indices en présence pour déterminer si le projet de mariage était, ou non, de complaisance (cf. arrêt attaqué, consid. 6a et 6c). Ils ne pouvaient conclure à l'absence de volonté des fiancés de fonder une communauté conjugale que si une telle conclusion s'imposait de manière manifeste au regard des circonstances. Mais tel n'est justement pas le cas en l'espèce à la lumière des constatations cantonales.
3.3 Certes, les déclarations des fiancés ne concordent pas sur certains points, en particulier sur la date de leur rencontre (août 2006 pour le fiancé et fin de l'année 2006 pour la fiancée) et sur les périodes où ils ont vécu ensemble en Suisse, à Z._, au domicile de Y._, avant que le recourant ne rentre au Kosovo en août 2008 pour déposer sa demande de visa; vrai est-il également que les intéressés se sont tous deux trompés sur l'activité professionnelle exercée par l'autre, le fiancé ayant notamment indiqué que son amie travaillait pour une compagnie d'assurance à Sion, alors qu'elle occupe un poste dans l'administration.
Les premiers juges ont toutefois constaté que les protagonistes avaient donné des réponses cohérentes quant à leurs loisirs à l'époque où ils avaient vécu ensemble en Valais et que le recourant savait dans quelle commune sa fiancée habitait, même s'il ne pouvait en donner l'adresse exacte; il avait également pu désigner la ville où elle travaillait et connaissait plusieurs des membres de sa famille dont il avait pu donner les noms. L'arrêt attaqué retient également que les fiancés ont entretenu des contacts téléphoniques réguliers (voix et sms) depuis le retour du recourant au Kosovo en août 2008, que Y._ s'est rendue en septembre 2009 et mai 2010 au Kosovo pour "revoir son fiancé et passer du temps avec celui-ci" et qu'elle lui a versé, "à tout le moins entre mars et juin 2009, plusieurs centaines de francs (...dans) le but de lui fournir une aide matérielle". Enfin, le Tribunal cantonal a constaté que le recourant avait produit en cause sept témoignages écrits émanant de l'entourage des fiancés attestant la réalité et l'intensité de leurs liens; malgré le risque de "collusion" pouvant exister entre les fiancés et les témoins, les premiers juges ont expressément considéré ces témoignages comme crédibles, car ils "comportent des détails significatifs du vécu et leur teneur est corroborée par d'autres pièces du dossier (factures téléphoniques, documents de voyage)".
Dans la mesure où l'on peut tenir pour établi que les intéressés ont cohabité pendant plusieurs mois jusqu'en août 2008 et qu'ils sont par la suite effectivement restés en contact, les imprécisions voire les divergences contenues dans leurs déclarations n'apparaissent guère déterminantes pour apprécier la réalité de leurs liens et leur volonté de fonder une communauté conjugale. A cet égard, on ne saurait suivre les premiers juges lorsqu'ils semblent accorder de l'importance au fait que les fiancés n'ont pas mentionné, dans leurs déclarations, "de projets en commun"; à une question aussi vague, il n'est pas étonnant que les intéressés n'aient pas pu fournir de réponse claire (la fiancée a répondu qu'ils envisageaient de "vivre en paix", "voyager" et "jardiner"), s'agissant de personnes dans la force de l'âge qui n'ont apparemment ni projet d'enfants communs ni projet d'acquisition immobilière.
3.4 En réalité, les démarches entreprises par Y._ pour faire venir son fiancé en Suisse, les déclarations de son entourage, ses voyages au Kosovo ainsi que ses transferts d'argent dans ce pays sont propres à établir que, de son côté en tout cas, le projet de mariage est sincère et ne vise pas à éluder les dispositions sur l'admission et le séjour des étrangers.
Certes suffit-il qu'un seul des fiancés ait en vue un mariage de complaisance pour refuser de célébrer l'union et/ou de reconnaître les droits qui y sont attachés en matière de police des étrangers. L'arrêt attaqué ne contient toutefois aucune constatation décisive permettant d'imputer avec évidence, comme le prescrit la jurisprudence, une telle intention au recourant. Il n'est notamment pas constaté que celui-ci profiterait de la fragilité psychique de sa fiancée ou que celle-ci appartiendrait à un groupe social marginal. Par ailleurs, qu'il ait sans succès tenté de régulariser sa situation en Suisse dans le passé et qu'il présente une notable différence d'âge avec sa fiancée sont des indices insuffisants pour qualifier de fictif son projet de mariage au vu des circonstances du cas (période de cohabitation des fiancés d'une certaine durée; maintien de leurs contacts après le départ du recourant au Kosovo; témoignages écrits probants sur la nature et l'intensité de leurs liens; délai d'une année et demie environ entre le moment de leur rencontre et la demande de visa litigieuse pour se marier en Suisse). Il convient également de constater (cf. art. 105 al. 2 LTF) que, lors de son interpellation le 2 mars 2011 sur un chantier à A._, le recourant a déclaré qu'il habitait depuis un mois chez sa fiancée à Z._; bien qu'illégal, ce séjour tend à confirmer le désir des fiancés de vivre de manière maritale.
3.5 En définitive, le Tribunal cantonal pouvait tout au plus concevoir un certain doute sur les véritables intentions matrimoniales des fiancés, en particulier du recourant; il ne disposait toutefois pas de suffisamment d'éléments pour conclure à leur absence manifeste de volonté de fonder une communauté conjugale; en confirmant le refus d'autorisation de séjour opposé au recourant pour ce motif, les premiers juges ont dès lors méconnu la notion de mariage de complaisance, singulièrement la retenue imposée par la jurisprudence pour retenir une telle qualification (cf. supra consid. 3.1, 3ème paragraphe).
4. Il suit de ce qui précède que le recours doit être admis dans la mesure où il est recevable et l'arrêt attaqué annulé, la cause étant renvoyée au Service cantonal pour qu'il rende une nouvelle décision sur le droit du recourant d'obtenir une autorisation de séjour - de courte durée - en vue de se marier en Suisse. Il lui appartiendra d'examiner si l'intéressé remplit les conditions requises à cet effet par l'art. 8 CEDH (cf. les arrêts cités supra au consid. 1.2.3). A cet égard, on relèvera qu'en l'absence d'indices suffisants permettant d'en douter, le mariage doit être qualifié de "sérieusement voulu" au sens de la jurisprudence. Le Service cantonal vérifiera également qu'au vu des démarches entreprises par les fiancés, le mariage peut être qualifié "d'imminent". Il s'assurera encore qu'il n'existe pas de motifs pouvant justifier, au terme d'une pesée des intérêts en présence, une restriction du droit en cause au sens de l'art. 8 par. 2 CEDH; à première vue, les seuls motifs ayant conduit à prononcer à l'égard du recourant une interdiction d'entrée jusqu'au 1er mars 2013 (séjour illégal et travail sans autorisation) ne semblent pas suffisants pour autoriser une telle ingérence dans la protection de sa vie privée et familiale. Notons enfin qu'en cas d'octroi de l'autorisation de séjour litigieuse, l'ODM sera en principe tenu de suspendre l'interdiction d'entrée prononcée à l'égard du recourant (cf. art. 67 al. 5 LEtr; arrêts 2C_793/2008 du 27 mars 2009 consid. 3.2 et 2C_473/2008 du 17 novembre 2008 consid. 2.3).
Il n'est pas perçu de frais judiciaires (cf. art. 66 al. 4 LTF). Obtenant gain de cause, le recourant a droit à une indemnité à titre de dépens à la charge du canton de Valais (cf. art. 68 al. 1 et 2) incluant un certain montant pour la procédure cantonale (cf. art. 68 al. 5 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Dans la mesure où il est recevable, le recours est admis et l'arrêt attaqué annulé, la cause étant renvoyée au Service de la population et des migrations du canton du Valais pour nouvelle décision au sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le canton du Valais versera au recourant un montant de 4'000 fr. à titre de dépens pour la procédure fédérale et cantonale.
4. Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations, au Conseil d'Etat et à la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 2 décembre 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Addy