Faits :
A. A._, ressortissant libyen né en 1979, est entré en Suisse le 20 novembre 1991 avec sa mère et ses deux frères pour y déposer une demande d'asile. Celle-ci a été rejetée le 20 janvier 1992, soit quelques mois après le rejet, le 4 octobre 1991, d'une demande d'asile présentée par le père du prénommé en janvier 1991. Le 13 août 1993, la Commission suisse de recours en matière d'asile a rejeté les différents recours formés par les membres de la famille A._ contre les refus d'asile prononcés à leur encontre et a ordonné leur renvoi de Suisse. A l'issue d'une demande de réexamen de leur situation, les intéressés ont été autorisés, par décision du 22 octobre 1997, à demeurer en Suisse au bénéfice d'une admission provisoire, leur renvoi en Libye n'apparaissant pas une mesure raisonnablement exigible.
B. Le 22 octobre 2000 au petit matin, après une nuit alcoolisée passée avec des amis, A._ a gravement blessé une personne avec un couteau à la suite d'une banale bousculade sur la voie publique qui a dégénéré. Il a été arrêté par la police et placé en détention préventive le même jour. A raison de ces faits, il a été condamné à une peine de 5 ans de réclusion pour crime manqué de meurtre et infraction à la législation fédérale sur les armes, sous déduction de 446 jours de détention préventive; cette peine était assortie d'une expulsion du territoire suisse pour une durée de 10 ans avec sursis pendant 5 ans; selon les constatations pénales, les événements se sont produits alors que l'auteur n'avait pourtant fait l'objet d'aucune menace et d'aucune provocation de la part de la victime, les juges parlant à cet égard d'acte gratuit, de mobile égoïste et de mentalité inquiétante (jugement du Tribunal correctionnel de l'arrondissement de Lausanne du 10 janvier 2002, confirmé sur recours par la Cour de cassation pénale du canton de Vaud le 17 mai 2002). Alors qu'il purgeait encore sa peine, A._ a été condamné à une peine complémentaire de 12 mois d'emprisonnement pour tentative d'agression, rixe, lésions corporelles simples qualifiées, complicité de contrainte et ivresse au volant; assortie d'une expulsion du territoire suisse pour une durée de 5 ans avec sursis pendant 5 ans, sous déduction de 19 jours de détention préventive effectués du 1er au 19 août 1999, cette peine sanctionnait des faits antérieurs à la première condamnation, en particulier une "expédition punitive" à laquelle l'intéressé avait pris part dans la nuit du 30 au 31 juillet 1999; il s'agissait plus exactement, selon les faits retenus par la justice pénale, d'une opération que l'intéressé avait "minutieusement préparée" et exécutée de concert avec ses deux frères et d'autres personnes et qui avait consisté à tendre un guet-apens en vue de donner une leçon ou du moins d'intimider une personne avec laquelle sa famille était en conflit; les auteurs étaient armés, toujours selon les constatations pénales, de bâtons de bois ("du type manche à pelle") et d'un tuyau métallique qu'ils avaient préalablement volés sur un chantier, et ils ont roué de coups leur victime qui avait tenté de se défendre à l'aide d'une arme blanche; A._ a joué un "rôle moteur" et même de "meneur principal" dans cette opération de justice privée et sa culpabilité a été jugée "lourde" (jugement du Tribunal correctionnel de l'arrondissement de Lausanne du 13 février 2003).
1 A._ a été libéré conditionnellement le 2 octobre 2004. Entre-temps, pendant sa détention, il a été mis au bénéfice d'une autorisation de séjour valable jusqu'au 6 juillet 2002, apparemment à la suite d'une erreur de l'autorité compétente. Par décision du 23 janvier 2004, le Service de la population du canton de Vaud (ci-après: le Service de la population) a refusé de prolonger cette autorisation au vu de la gravité des condamnations prononcées contre l'intéressé. Sur recours, cette décision a été confirmée par le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif) dans un arrêt du 14 décembre 2004. Le 4 février 2005, le Tribunal fédéral a déclaré irrecevable un recours formé contre l'arrêt précité du Tribunal administratif (arrêt 2A.64/2005).
C. Le 8 février 2005, A._ a déposé une demande d'admission provisoire, en faisant valoir que son renvoi en Libye n'était pas possible. Le 14 février suivant, il a épousé B._, une ressortissante portugaise née en 1982 à Porto, qui vit en Suisse depuis de nombreuses années et bénéficie d'un permis d'établissement depuis le mois de juillet 1994. Le 10 octobre 2005, A._ a formé une demande d'autorisation de séjour par regroupement familial fondée sur l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ci-après: Accord sur la libre circulation des personnes ou Accord ou ALCP; RS 0.142.112.681).
2 Par décision du 1er mars 2006, le Service de la population a refusé à A._ l'octroi de toute autorisation de séjour au vu de ses antécédents pénaux. Saisi d'un recours des époux A._, le Tribunal administratif l'a rejeté, par arrêt du 26 janvier 2007, en retenant notamment que l'Accord sur la libre circulation des personnes n'était pas applicable, car l'épouse était arrivée en Suisse avant son entrée en vigueur.
D. Les époux A._ forment un recours en matière de droit public contre l'arrêt précité du Tribunal administratif dont ils requièrent la réforme, sous suite de frais et dépens, en ce sens qu'une autorisation de séjour CE/AELE soit octroyée à A._ avec effet au 14 février 2005 (date du mariage); à titre subsidiaire, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause au Tribunal administratif ou au Service de la population pour nouvelle décision dans le sens de leur conclusion principale. Ils invoquent la violation aussi bien de l'Accord sur la libre circulation des personnes que de l'art. 8 de la Convention de sauvegarde des droits de l'homme et des libertés fondamentales du 4 novembre 1950 (CEDH; RS 0.101).
3 Le Service de la population a renoncé à se déterminer sur le recours, tandis que l'Office fédéral des migrations en propose le rejet. Le Tribunal administratif se réfère aux considérants de son arrêt.
E. Par ordonnance du 4 avril 2007, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif requise par le recourant.

Le Tribunal fédéral considère en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis.
1.1 L'arrêt entrepris ayant été rendu après l'entrée en vigueur de la loi du 17 juin 2005 sur le Tribunal fédéral (LTF; RS 173.110), la procédure est régie par le nouveau droit (<ref-law>).
1.2 D'après l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral, ni le droit international, ne donnent droit.
1 En sa seule qualité de conjoint d'une ressortissante portugaise, le recourant peut, en principe, déduire un droit à une autorisation de séjour en Suisse des art. 7 lettre d ALCP et 3 par. 1 et 2 lettre a annexe I ALCP (cf. <ref-ruling> consid. 4.1 et 8.3 pp. 116 et 129 et les arrêts cités). Comme son épouse bénéficie d'un permis d'établissement, il peut également fonder un tel droit sur l'art. 17 al. 2 LSEE voire, en relation avec l'<ref-law>, directement sur l'art. 7 al. 1 LSEE (cf. infra consid. 3.6 in fine et les arrêts cités). Enfin, il n'est pas contesté que le recourant forme une véritable union conjugale avec son épouse, de sorte qu'il peut aussi invoquer le droit à la protection de la vie familiale découlant de l'art. 8 par. 1 CEDH (cf. <ref-ruling> consid. 5 p. 269). Le recours est dès lors recevable du chef des dispositions précitées.
1.3 Par ailleurs, comme destinataire direct de l'arrêt attaqué, le recourant a sans conteste qualité pour recourir au sens de l'<ref-law>. Quant à son épouse, étant elle-même empêchée de vivre avec lui en Suisse, elle est également touchée, de manière indirecte, par la décision attaquée. Comme elle était déjà partie à la procédure cantonale, la qualité pour recourir en procédure fédérale doit par conséquent aussi lui être reconnue (cf., sous l'ancien droit de procédure, les arrêts du 23 avril 2004, 2A.240/2003, consid. 1.3; du 9 octobre 1998, 2A.383/1998, consid. 2c; du 30 septembre 1998, 2A.103/1998, consid. 1c).
1.4 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), le recours est recevable en vertu des <ref-law>.
2. Le Tribunal administratif a estimé que le recourant ne pouvait pas se prévaloir de l'Accord sur la libre circulation des personnes, car son épouse était déjà établie de longue date en Suisse lors de l'entrée en vigueur de ce texte le 1er juin 2002. Cette opinion est erronée. Le champ d'application personnel et temporel de l'Accord ne dépend en effet pas du moment auquel un ressortissant communautaire arrive ou est arrivé en Suisse, mais seulement de l'existence d'un droit de séjour garanti par l'Accord au moment déterminant, soit lorsque le droit litigieux - tel qu'en l'espèce le regroupement familial - est exercé. Autrement dit, les ressortissants communautaires résidant déjà en Suisse lors de son entrée en vigueur peuvent se prévaloir de l'Accord dès qu'ils relèvent de l'une ou l'autre des situations de libre circulation prévues à cet effet et qu'ils remplissent les conditions afférentes à leur statut (cf. <ref-ruling> consid. 3.4 p. 7 et les références citées). En l'espèce, du moment qu'elle exerce une activité salariée, l'épouse du recourant peut, en principe, déduire de l'Accord le droit à une autorisation de séjour (cf. <ref-law> et les art. 2 et 6 ss annexe I ALCP). Dans cette mesure, elle peut également, si les conditions en sont réunies, exercer les "autres droits" découlant de son statut (cf. art. 7 lettre d ALCP) et, en particulier, obtenir une autorisation de séjour en faveur de son conjoint au titre du regroupement familial prévu à l'art. 3 par. 2 lettre a annexe I ALCP.
3. 3.1 Partie intégrante de l'Accord sur la libre circulation des personnes (cf. <ref-law>), l'art. 3 par. 1 et 2 annexe I ALCP règle le droit de séjour des membres de la famille des ressortissants communautaires; il prévoit notamment que, quelle que soit leur nationalité, leur conjoint a en principe le droit de "s'installer" avec eux. Ce droit est calqué sur les art. 10 et 11 du Règlement (CEE) 1612/68, si bien que, conformément à l'<ref-law>, son interprétation doit se faire en tenant compte de la jurisprudence antérieure au 21 juin 1999 qui a été rendue en la matière par la Cour de justice des Communautés européennes (ci-après: la Cour de justice ou CJCE; au sujet de la prise en considération d'arrêts de la Cour de justice postérieurs à cette date, cf. <ref-ruling> consid. 3.6 p. 9 ss, 113 consid. 5.2 p. 119 s. et les références citées).
2 S'inspirant d'une jurisprudence de la Cour de justice postérieure au 21 juin 1999 dans une affaire concernant l'art. 10 du Règlement (CEE) 1612/68 (arrêt du 23 septembre 2003, Akrich, C-109/01, Rec. 2003, p. I-9607, également reproduit in EuGRZ 2003 p. 607 ss), le Tribunal fédéral a précisé que l'<ref-law> n'est pas applicable lorsqu'au moment où le droit au regroupement familial est exercé, le membre de la famille visé par la demande n'a pas la nationalité d'un Etat membre et ne réside pas déjà légalement dans un Etat membre; en fait, il serait plus exact, dans le cadre des relations entre la Suisse et l'Union européenne, de parler de partie contractante (à l'Accord) que d'Etat membre; autrement dit, l'exercice du droit prévu par la disposition précitée présuppose, pour les ressortissants non communautaires, qu'ils puissent justifier d'un séjour légal préalable dans une partie contractante (cf. <ref-ruling> consid. 3.6, p. 9 ss). Ne remplit notamment pas une telle condition (préalable) l'époux étranger d'une ressortissante communautaire qui n'a jamais résidé légalement dans une partie contractante et qui fait l'objet en Suisse, au moment déterminant, d'une décision de refus d'autorisation de séjour entrée en force assortie d'une mesure de renvoi du territoire suisse (cf. arrêts du 23 avril 2004, 2A.114/2003, consid. 3.3 et du 2 août 2004, 2A.7/2004, consid. 3.3); le fait qu'il ait bénéficié d'une admission provisoire ou que sa présence ait été tolérée pendant un certain temps ne saurait, en principe, remplir la condition du séjour légal préalable (arrêts précités; en ce sens, voir aussi: Richard Plender, Quo vadis-, Nouvelle orientation des règles sur la libre circulation des personnes suivant l'affaire Akrich, in Cahiers de droit européen, 2004, p. 261 ss, p. 276; Matthew Elsmore/Peter Starup, Case C-1/05, Yunying Jia v. Migrationsverket, Judgement of the Cour (Grand Chamber), 9 January 2007, in Common Market Law Review, vol. 44, juin 2007, p. 787 ss, p. 794). Néanmoins, l'époux d'une ressortissante communautaire qui a contesté par la voie d'un recours une décision refusant de prolonger une (première) autorisation de séjour valablement délivrée en Suisse est réputé résider légalement dans notre pays pendant toute la durée de la procédure contentieuse et peut, à ce titre, en principe tirer pleinement avantage des droits prévus par l'Accord (cf. arrêt du 6 août 2004, 2A.94/2004, consid. 2).
3.2 En l'espèce, A._ a été mis au bénéfice, le 11 octobre 2001, d'une autorisation de séjour valable jusqu'au 6 juillet 2002. Que l'octroi de cette autorisation résultât apparemment d'une erreur n'est pas décisif pour décider si le recourant résidait légalement en Suisse au moment - déterminant - de la demande de regroupement familial: en effet, le permis en question n'a nullement été révoqué et il n'apparaît pas non plus qu'il fût frappé de nullité absolue. En revanche, il faut constater que le recours entrepris contre le refus de prolonger cette première autorisation de séjour a été définitivement écarté par le Tribunal fédéral (arrêt du 4 février 2005, cause 2A.64/2005). Depuis le 6 juillet 2002, le recourant est donc en Suisse au bénéfice d'une simple tolérance, qui découle notamment de l'effet suspensif attaché aux différentes procédures qu'il a engagées, jusqu'ici vainement, en vue d'obtenir la régularisation de sa situation (recours contre le refus de prolongation de l'autorisation de séjour; demande d'admission provisoire; demande d'autorisation de séjour au titre du regroupement familial). Par ailleurs, sa demande de regroupement familial - ici litigieuse - fondée sur l'<ref-law> a été formée le 10 octobre 2005, soit plusieurs mois après l'entrée en force - le 4 février 2005 - de la décision refusant de prolonger son autorisation de séjour arrivée à échéance le 6 juillet 2002. Partant, le recourant ne saurait prétendre qu'il résidait légalement en Suisse au moment déterminant, et il doit se laisser opposer les conséquences de l'arrêt Akrich précité, à savoir que son éventuel droit à une autorisation de séjour doit s'examiner à la lumière des seules dispositions du droit interne et de l'art. 8 CEDH (cf. arrêt précité du 23 avril 2004, 2A.114/2003, consid. 3.3).
3.3 Le recourant remet cependant en cause les conséquences que le Tribunal fédéral a tirées de l'arrêt Akrich précité. A ses yeux, ce précédent ne viserait que le cas très particulier circonscrit par l'état de fait qui en est à l'origine et n'aurait ainsi pas pour effet de subordonner de manière générale l'octroi d'une autorisation de séjour fondée sur l'<ref-law> à la condition que les ressortissants de pays tiers, parents de ressortissants communautaires, disposent au préalable d'un titre de séjour délivré par une partie contractante. A l'appui de son point de vue, le recourant se réfère, en réplique et sans y avoir été invité (cf. sa lettre du 4 mai 2007), à un récent arrêt de la Cour de justice (Yunying Jia v. Migrationsverket, du 9 janvier 2007, C-1/05), postérieur, comme l'arrêt Akrich, à l'entrée en vigueur de l'Accord (sur cette particularité, cf. infra consid. 3.5.2).
3.4 Le contexte de l'affaire Jia (précitée) est le suivant: le 13 mai 2003, Yunying Jia, ressortissante chinoise dont le fils vit en Suède avec son épouse de nationalité allemande, est entrée dans ce pays au bénéfice d'un visa de tourisme valable pendant 90 jours au maximum; le 7 août suivant, elle a demandé un titre de séjour en se prévalant de son lien de parenté avec l'épouse de son fils et de sa situation de dépendance économique par rapport à ce dernier. L'autorité suédoise compétente a refusé de faire droit à cette demande, au motif que la situation de dépendance économique invoquée n'était pas suffisamment établie. Yunying Jia ayant fait appel de ce refus, l'autorité de recours suédoise saisie a soumis à la Cour de justice différentes questions destinées à éclaircir la portée de l'arrêt (précité) Akrich. Après les avoir reformulées et réunies en une seule, la Cour de justice a répondu aux questions posées de la manière suivante: "Le droit communautaire, eu égard à l'arrêt Akrich, n'impose pas aux Etats membres de soumettre l'octroi d'un droit de séjour à un ressortissant d'un pays tiers, membre de la famille d'un ressortissant communautaire ayant fait usage de sa liberté de circulation, à la condition que ce membre de la famille ait, au préalable, séjourné légalement dans un autre Etat membre." Les juges ont en effet estimé que la condition de séjour préalable telle que formulée dans l'arrêt Akrich ne pouvait pas être transposée au cas de Yunying Jia, car il n'était reproché à cette dernière ni de séjourner illégalement dans un Etat membre, ni de chercher à se soustraire abusivement à l'emprise d'une réglementation nationale en matière d'immigration. Au contraire d'Hacene Akrich, l'intéressée se trouvait légalement en Suède lorsqu'elle a introduit sa demande et le droit suédois ne s'opposait pas, dans sa situation, à l'octroi d'un droit de séjour de longue durée en sa faveur (arrêt précité Jia, points 28 à 33).
3 En disant que le droit communautaire "n'impose pas" aux Etats membres, dans les circonstances de l'affaire Jia, de subordonner l'octroi d'un titre de séjour aux ressortissants de pays tiers à la condition d'un séjour légal préalable dans un (autre) Etat membre, la Cour de justice ne paraît pas - a contrario - vouloir leur interdire de prévoir une telle exigence dans leur législation (sur la pertinence d'une telle interprétation, cf. Jean-Yves Carlier, La libre circulation des personnes dans l'Union européenne, in Journal des tribunaux, Droit européen, 2007, p. 80 ss, p. 85; Elsmore/Starup, op. cit., p. 793 ss, p. 797). C'est du reste apparemment ce qu'ont fait le Royaume-Uni et le Danemark à la suite de l'arrêt Akrich (cf. Elsmore/Starup, op. cit., p. 800 s.; cf. Hanspeter Mock/Fabrice Filliez, Libre circulation des personnes et regroupement familial: à propos de la prise en compte de la jurisprudence de la Cour de Luxembourg par le Tribunal fédéral, in RSDIE, 2006, p. 237 ss, p. 248 ad note de bas de page no 41). En toute hypothèse, les différences que la Cour de justice a mises en évidence, dans l'affaire Jia, dans sa comparaison avec les faits à la base de l'arrêt Akrich, laissent clairement entrevoir que les demandes de regroupement familial précédées - comme en l'espèce - d'un séjour illégal dans un Etat membre ou destinées à contourner une législation nationale en matière d'immigration ne doivent pas bénéficier des avantages du droit communautaire (cf. arrêt précité Jia, points 28 à 33 a contrario; Elsmore/Starup, op. cit., p. 796); cette analyse s'impose même dans l'approche restrictive - que défend le recourant - consistant à envisager l'arrêt Akrich, à la lumière de l'affaire Jia, comme un simple cas d'espèce qui ne poserait pas le séjour légal préalable dans un Etat membre comme une condition générale prévue par le droit communautaire pour bénéficier de ses facilités en matière de regroupement familial (cf. Eleanor Spaventa, Case C-109/01, Secretary of State for the Home Department v. H. Akrich, judgment of the Full Court of 23 September 2003, in Common Market Law Review, 2005, p. 225 ss, spécialement p. 233 et 238; Carlier, op. cit., p. 84 s.).
3.5 En réalité, les arrêts Akrich et Jia ne se laissent pas facilement interpréter et font suite à une série de décisions rendues par la Cour de justice où, dans des affaires à la croisée des ordres juridiques communautaire et nationaux, les juges européens ont semblé partagés entre, d'une part, la volonté de favoriser le plus possible l'objectif (communautaire) de libre circulation des personnes à l'intérieur des Etats membres et, d'autre part, la nécessité de respecter et préserver les prérogatives (nationales) des Etats membres en matière de politique d'immigration. Bien que normalement distinctes, ces deux "logiques" peuvent en effet se chevaucher dans certaines circonstances, notamment lorsque le ressortissant d'un pays tiers, parent d'un citoyen de l'Union ayant fait usage de sa liberté de circuler, demande à rejoindre ce dernier dans un Etat membre au titre du droit communautaire (cf. Emmanuelle Broussy/Francis Donnat/Christian Lambert, Droit de séjour et immigration, in L'actualité juridique - Droit administratif [AJDA], p. 295 ss). Certains auteurs parlent à ce propos de "dilemme" (cf. Monique Luby, Chronique de jurisprudence du Tribunal et de la Cour de justice des Communautés européennes, in Journal du droit international 2004, p. 580, citant l'avocat général Geelhoed; Plender, op. cit., p. 268), tandis que d'autres évoquent une "tension" entre les politiques nationales d'immigration - toujours plus sévères - et les avancées de la libre circulation (cf. Mock/Filliez, op. cit., p. 247). Dans l'arrêt Akrich, la Cour de justice avait clairement pris position en faveur du respect des compétences nationales des Etats membres en matière d'immigration, en affirmant que "le règlement 1612/68 ne vise que la libre circulation à l'intérieur de la Communauté (mais) est muet sur l'existence des droits d'un ressortissant d'un pays tiers, conjoint d'un citoyen de l'Union, quant à l'accès au territoire de la Communauté" (point 49).
3.5.1 Cela étant, il n'y a pas de motif de revenir sur la jurisprudence publiée aux <ref-ruling> dans la ligne de l'arrêt Akrich, et ce pour les raisons suivantes.
3.5.2 Premièrement, la portée de l'arrêt Jia n'est, comme on l'a vu, pas claire (cf., à ce sujet, les trois interprétations proposées par Elsmore/Starup, op. cit., p. 793 ss), et il n'est pas certain que, comme le soutient le recourant, le cas Akrich soit dorénavant relégué au simple rang d'arrêt d'espèce (cf. Broussy/Donnat/Lambert, op. cit., p. 297). A ce jour, ce précédent fait du reste toujours l'objet de demandes d'interprétation de la part des juridictions nationales des Etats membres (cf. les conclusions présentées le 5 juillet 2007 par l'avocat général Mengozzi, dans l'affaire C-291/05, Minister voor Vreemdelingenzaken en Integratie c./Rachel Nataly Geradina Eind, en particulier les points 43 à 50).
3.5.3 Deuxièmement, indépendamment des problèmes d'interprétation que posent les arrêts Akrich et Jia (notamment en relation avec le sens et la portée de la condition du séjour légal préalable, cf. Carlier, op. cit., p. 85; Spaventa, op. cit., p. 232 s.; Elsmore/Starup, op. cit., p. 792 ss), ceux-ci sont tous deux postérieurs à l'entrée en vigueur de l'Accord sur la libre circulation des personnes. Le Tribunal fédéral n'est dès lors pas tenu de les prendre en compte pour interpréter l'<ref-law> (cf. <ref-law> a contrario). Il n'a d'ailleurs fait que se référer à l'arrêt Akrich dans la cause publiée aux <ref-ruling>. Et la même réserve vaut évidemment pour les prochaines décisions que rendra la Cour de justice en la matière, d'autant que les critiques émises contre la solution adoptée dans l'arrêt Akrich tiennent, pour certaines d'entre elles, à des questions de cohérence propres à l'ordre juridique communautaire, notamment par rapport au statut de citoyen de l'Union européenne (cf. Luby, op. cit., p. 581) ou par rapport à de récents actes communautaires entrés en vigueur après l'arrêt Akrich, comme la directive 2003/86/CE du Conseil, du 22 septembre 2003, relative au droit au regroupement familial, ou la directive 2004/38/CE du Parlement européen et du Conseil, du 29 avril 2004, relative au droit des citoyens de l'Union et des membres de leurs familles de circuler et de séjourner librement sur le territoire des États membres, modifiant le Règlement (CEE) 1612/68 et abrogeant les directives 64/221/CEE, 68/360/CEE, 72/194/CEE, 73/148/CEE, 75/34/CEE, 75/35/CEE, 90/364/CEE, 90/365/CEE et 93/96/CEE (cf. Elsmore/Starup, op. cit., p. 796; Mock/Filliez, op. cit., p. 252 s.; pour un aperçu de ces nouvelles règles, cf. Astrid Epiney/Andrea Faeh, Zum Aufenthaltsrecht von Familienangehörigen im europäischen Gemeinschaftsrecht, in Annuaire du droit de la migration, 2005/2006, p. 49 ss).
3.5.4 Troisièmement, les règles en matière de regroupement familial ici litigieuses sont calquées sur le Règlement (CEE) 1612/68 et visent, à l'avenant de ce texte au plan des relations communautaires, à permettre et favoriser la libre circulation des ressortissants des Etats membres de la Communauté européenne et de la Suisse "sur le territoire des parties contractantes" (cf. le préambule de l'Accord et son art. 1er; <ref-ruling> consid. 3.3 p. 6, 113 consid. 5.1 et 5.2 p. 118 ss). Ces règles ne sauraient dès lors interférer dans la politique migratoire de la Suisse - en principe réglée par le seul droit interne pour les ressortissants de pays tiers - au-delà de ce qui est nécessaire à la réalisation de l'objectif de libre circulation poursuivi par l'Accord. Or, la condition du séjour légal préalable telle qu'interprétée par le Tribunal fédéral est conforme à la finalité de l'<ref-law> ou, pour reprendre la terminologie de la Cour de justice, ne prive pas cette norme de son "effet utile". Celle-ci tend en effet à garantir aux ressortissants communautaires que les membres de leur famille, même s'ils n'ont pas la nationalité d'une partie contractante, puissent les accompagner en Suisse s'ils décident d'exercer les droits prévus par l'Accord sur la libre circulation des personnes. En l'absence d'une telle garantie, les ressortissants communautaires pourraient en effet être dissuadés d'exercer ces droits, par crainte que la réglementation suisse en matière d'immigration ne les sépare de leur famille (cf. <ref-ruling> consid. 7.1 p. 124 s. et 7.3 p. 126 et les références citées). Mais la situation se présente sous un jour différent pour les membres de la famille d'un ressortissant communautaire qui, au moment où celui-ci exerce son droit à la libre circulation, ne vivaient pas déjà légalement avec lui dans une partie contractante; en effet, le ressortissant communautaire placé dans une telle situation ne saurait alors prétendre être dissuadé d'exercer sa liberté de circulation par la crainte de perdre un avantage, dans la mesure où les membres de sa famille ayant la nationalité d'un pays tiers n'ont de toute façon, au moment de la demande, aucun droit de séjour dans quelque partie contractante que ce soit (cf. <ref-ruling> consid. 3.6.1 p. 9 s. et 3.6.3 p. 11 ss; Plender, op. cit., p. 280). Dans cette mesure, l'interprétation de l'arrêt Akrich permet, sans trahir ni la lettre ni l'esprit de l'Accord, de ménager les prérogatives de la Suisse en matière de politique migratoire, en même temps que de tracer une limite claire entre les situations relevant du seul droit interne (et de l'art. 8 CEDH) et celles entrant dans le champ d'application de l'Accord (sur ces aspects considérés du point de vue du droit communautaire, cf. Broussy/Donnat/Lambert, op. cit., p. 297).
3.5.5 Enfin, cette solution a également l'avantage d'éviter dans une large mesure les situations de discrimination à rebours pouvant se présenter en matière de regroupement familial: qu'elles émanent de citoyens suisses ou de ressortissants communautaires, les demandes d'autorisations de séjour en faveur de parents originaires de pays tiers qui ne résident pas déjà légalement dans une partie contractante sont en effet traitées de la même manière, soit par référence au droit interne et à l'art. 8 CEDH (cf. Mock/Filliez, op. cit., p. 238 s.; Broussy/Donnat/Lambert, op. cit., p. 297). Or, l'objectif d'éviter la discrimination à rebours fait partie des préoccupations du législateur suisse, comme l'atteste la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RO 2007 5437), approuvée le 24 septembre 2006 en votation populaire (FF 2006 8953), qui entrera en vigueur - sous réserve de quelques dispositions - le 1er janvier 2008 (RO 2007 5487). Cette nouvelle loi vise en effet, en matière de regroupement familial de parents originaires de pays tiers, à conférer aux ressortissants suisses des droits analogues à ceux prévus pour les ressortissants communautaires à l'<ref-law> (cf. message concernant la loi sur les étrangers du 18 mars 2002, in FF 2002 3469 ss, p. 3510; Minh Son Nguyen, Le regroupement familial dans la loi sur les étrangers et dans la loi sur l'asile révisée, in Annuaire du droit de la migration, 2005/2006, p. 31 ss, p. 38 s.). Afin de tenir compte des répercussions de l'<ref-ruling>, les Chambres fédérales ont même modifié le projet initial du Conseil fédéral et étendu aux membres étrangers de la famille d'un ressortissant suisse qui souhaitent obtenir un droit de séjour en Suisse la condition de justifier au préalable "d'une autorisation de séjour durable délivrée par un Etat avec lequel la Suisse a conclu un accord sur la libre circulation des personnes" (cf. art. 42 al. 2 LEtr; session de printemps du Conseil des Etats, 16 mars 2005, in BO CE 2005, p. 303 s. [proposition de la majorité de la Commission et intervention de Trix Heberlein]; session d'automne du Conseil national, 28 septembre 2005, in BO CN 2005 p. 1233 ss [proposition de la majorité de la Commission et interventions de Geri Müller, Philipp Müller, et Serge Beck]). Autrement dit, l'abandon de la jurisprudence précitée aurait pour conséquence - paradoxale - de replacer les ressortissants suisses, à partir du 1er janvier 2008, dans une moins bonne situation que les citoyens communautaires quant au droit d'obtenir une autorisation de séjour pour les membres étrangers de leur famille, en violation de la volonté du législateur. C'est là une raison de plus qui justifie de maintenir les conséquences tirées de l'arrêt Akrich à l'<ref-ruling>.
3.6 En conséquence, l'<ref-law> n'est, comme l'a jugé le Tribunal administratif, mais pour d'autres motifs, pas applicable au recourant. Cependant, compte tenu de la portée générale que revêt le principe de non-discrimination inscrit à l'<ref-law>, l'épouse portugaise du recourant, qui est également partie à la présente procédure aux côtés de ce dernier, ne doit pas être moins bien traitée que ne le serait l'épouse suisse d'un ressortissant étranger. Or, l'art. 7 al. 1 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142.20) ne prévoit l'extinction du droit à l'autorisation de séjour accordée à l'époux étranger d'une ressortissante suisse que s'il existe à son égard un "motif d'expulsion" (cf. art. 7 al. 1 LSEE), tandis qu'en l'absence d'un titre de séjour fondé sur l'Accord, comme en l'espèce, une simple infraction à "l'ordre public" (cf. art. 17 al. 2 LSEE) est déjà susceptible d'entraîner une telle conséquence pour l'époux étranger d'une ressortissante communautaire au bénéfice d'un permis d'établissement (sur cette différence, cf. <ref-ruling> consid. 3a p. 390; <ref-ruling> consid. 4a p. 130/131; Philip Grant, La protection de la vie familiale et de la vie privée en droit des étrangers, thèse Genève 2000, p. 190/191). Il convient dès lors d'examiner l'éventuel droit du recourant à l'octroi d'une autorisation de séjour à la lumière des art. 7 al. 1 LSEE et 8 CEDH (cf. arrêts du 25 août 2005, 2A.325/2004, consid. 3.3 et 4; du 2 août 2004, 2A.7/2004, consid. 3.3 et 4.1; du 23 avril 2004, 2A 114/2003, consid. 4).
4. 4.1 Aux termes de l'art. 7 al. 1 (première phrase) LSEE, le conjoint étranger d'un ressortissant suisse a droit à l'octroi et à la prolongation d'une autorisation de séjour ou d'établissement; ce droit s'éteint cependant lorsqu'il existe un motif d'expulsion (disposition précitée, troisième phrase). D'après l'art. 10 al. 1 LSEE, l'étranger peut être expulsé de Suisse ou d'un canton, notamment s'il a été condamné par une autorité judiciaire pour crime ou délit (lettre a) ou si sa conduite dans son ensemble et ses actes permettent de conclure qu'il ne veut pas s'adapter à l'ordre établi dans le pays qui lui offre l'hospitalité ou qu'il n'en est pas capable (lettre b). Le refus d'octroyer une autorisation de séjour ou d'établissement au conjoint étranger d'un ressortissant suisse (ou communautaire) sur la base de l'une des causes énoncées à l'art. 10 LSEE suppose une pesée des intérêts en présence et l'examen de la proportionnalité de la mesure (cf. art. 11 al. 3 LSEE; <ref-ruling> consid. 3c p. 117). Pour apprécier ce qui est équitable, l'autorité tiendra en particulier compte de la gravité de la faute commise par l'étranger, de la durée de son séjour en Suisse et du préjudice qu'il aurait à subir avec sa famille du fait de l'expulsion (art. 16 al. 3 RSEE) - respectivement du fait du refus d'accorder ou de prolonger une autorisation de séjour ou d'établissement.
La réglementation prévue par l'art. 8 CEDH est similaire: le droit au respect de la vie familiale (par. 1) n'est en effet pas absolu, en ce sens qu'une ingérence dans l'exercice de ce droit est possible selon l'art. 8 par. 2 CEDH, pour autant que celle-ci soit "prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale, ou à la protection des droits et libertés d'autrui". Il y a donc également lieu ici de procéder à une pesée des intérêts en présence (cf. <ref-ruling> consid. 2e, p. 639; <ref-ruling> consid. 2, p. 5/6; <ref-ruling> consid. 4b p. 131, 22 consid. 4a p. 24 s.).
4.2 Dans la pesée des intérêts, il faut en premier lieu tenir compte, en cas de condamnation de l'étranger pour crime ou délit, de la gravité des actes commis ainsi que de la situation personnelle et familiale de l'intéressé. La peine infligée par le juge pénal est le premier critère servant à évaluer la gravité de la faute et à peser les intérêts (cf. <ref-ruling> consid. 4c p. 15/16). Il y a lieu ensuite d'examiner si l'on peut exiger des membres de la famille qui ont un droit de présence en Suisse qu'ils suivent l'étranger dont l'autorisation de séjour est refusée. Pour trancher cette question, l'autorité compétente ne doit pas statuer en fonction des convenances personnelles des intéressés, mais prendre objectivement en considération leur situation personnelle et l'ensemble des circonstances. Si l'on ne peut pas exiger des membres de la famille pouvant rester en Suisse qu'ils partent à l'étranger, cet élément doit entrer dans la pesée des intérêts en présence mais n'exclut pas nécessairement, en lui-même, un refus de l'autorisation de séjour (cf. ATF <ref-ruling> consid. 2 p. 6; <ref-ruling> consid. 4b p. 131).
4.3 En l'espèce, les faits reprochés au recourant sont particulièrement graves et ont du reste été lourdement sanctionnés d'une peine de cinq ans de réclusion complétée d'une peine d'une année d'emprisonnement. Selon la jurisprudence applicable au conjoint étranger d'un ressortissant suisse, une condamnation à deux ans de privation de liberté constitue la limite à partir de laquelle, en général, il y a lieu de refuser l'autorisation de séjour, du moins quand il s'agit d'une demande d'autorisation initiale ou d'une requête de prolongation d'autorisation déposée après un séjour de courte durée (<ref-ruling>76 consid. 4.1 p. 185; <ref-ruling> consid. 4b p. 14). Certes, le recourant est arrivé en Suisse au mois d'octobre 1991, à l'âge de douze ans. Il apparaît cependant qu'il n'a bénéficié que tardivement d'une première autorisation de séjour, soit après août 2001, et que celle-ci lui a apparemment été délivrée par erreur; auparavant, il a résidé en Suisse sans titre de séjour ou, à partir du mois d'octobre 1997, au bénéfice d'une simple admission provisoire; par ailleurs, il a été arrêté et incarcéré du 22 octobre 2000 au 2 octobre 2004. Bien que relativement importante dans l'absolu, la durée de son séjour en Suisse doit dès lors être fortement relativisée: les années passées dans l'illégalité, en prison ou au bénéfice d'une simple tolérance ne sont en effet pas déterminantes dans la pesée des intérêts (cf. <ref-ruling> consid. 4.6 p. 503, 39 consid. 4 p. 43).
4 Quoi qu'il en soit, les peines infligées au recourant dépassent si largement la limite (indicative) de deux ans fixée par la jurisprudence que seules des circonstances tout à fait exceptionnelles seraient de nature à contrebalancer la gravité des fautes reprochées. Or, l'on cherche en vain de telles circonstances. Que l'intéressé se soit apparemment bien comporté depuis sa libération conditionnelle n'est à cet égard pas décisif; c'est même le moins que l'on pouvait attendre de lui. Par ailleurs, au contraire de la pratique en cours pour les étrangers bénéficiant d'un titre de séjour fondé sur l'Accord, le risque de récidive ne joue pas un rôle déterminant pour les mesures d'éloignement prises sur la base du droit interne, mais ne constitue qu'un facteur parmi d'autres dans la pesée des intérêts, où la gravité des actes commis est, comme on l'a vu, le premier élément à prendre en considération.
5 Au demeurant, le risque de récidive doit, en l'espèce, s'apprécier de manière rigoureuse, car les faits reprochés sont graves (cf. <ref-ruling> consid. 4c p. 15/16). A cela s'ajoute que les antécédents pénaux du recourant incitent à la plus grande réserve sur ce point. Il apparaît en effet qu'entre le mois de septembre 1998 (tentative de contrainte; cf. jugement du Tribunal correctionnel du 13 février 2003, p. 54) et le 22 octobre 2000 (date de son incarcération), l'intéressé s'est rendu coupable de plusieurs infractions, dont le degré de gravité est allé crescendo pour les principales, soit celles contre la vie et l'intégrité corporelle. Par ailleurs, il faut relever que l'infraction la plus grave, soit le crime manqué de meurtre, a été commise alors que son auteur était déjà inculpé pour des faits qui lui vaudront par la suite une année d'emprisonnement (notamment pour tentative d'agression, rixe et lésions corporelles simples qualifiées) et qu'il avait alors déjà subi 19 jours de détention préventive en août 1999 à raison de ces mêmes faits. En outre, tant le contexte général et le mode opératoire des infractions reprochées (violence et gravité des faits) que leur mobile (honneur; actes gratuits ou de justice privée; cf. supra état de fait ad lettre B) jettent une lumière défavorable sur le recourant et le font apparaître comme un individu dénué de sens moral, dangereux et prêt, selon les termes des juges pénaux "en toute circonstance, à jouer du muscle" (cf. jugement précité du Tribunal correctionnel, p. 65).
6 Enfin, indépendamment même de ses crimes, le recourant ne semble pas s'être intégré à la société suisse. En particulier, au plan professionnel, il n'a apparemment pas été capable d'occuper durablement une place de travail lui permettant de subvenir à ses besoins et les faits retenus au pénal laissent entrevoir un mode de vie et des fréquentations peu recommandables; par ailleurs, il n'a pas fourni de gages ou d'éléments concrets permettant de penser que la situation avait notablement changé ou pouvait se retourner. Certes, au plan familial, lorsque l'arrêt attaqué a été rendu, il était marié depuis près d'une année, et l'on peut concevoir qu'il sera difficile pour son épouse - également recourante - de le suivre à l'étranger, du moins s'il était finalement amené à vivre en Libye après son départ de la Suisse. Au vu des circonstances, cet obstacle n'apparaît cependant pas déterminant dans la pesée des intérêts, d'autant que, nonobstant ses dénégations, son épouse ne pouvait pas ignorer, au moment où elle s'est mariée, qu'il risquait de devoir quitter la Suisse: en effet, il était alors sous le coup d'une décision de refus d'autorisation de séjour rendue plus d'une année auparavant et entrée en force définitive de chose jugée quelques jours avant la célébration du mariage (arrêt du Tribunal fédéral du 4 février 2005).
4.4 Dans ces conditions, l'intérêt public à l'éloignement du recourant l'emporte sur son intérêt privé et celui de son épouse à ce qu'il puisse demeurer en Suisse.
5. Il suit de ce qui précède que le recours, entièrement mal fondé, doit être rejeté.
6. Succombant, les recourants doivent supporter les frais judiciaires (cf. art. 65 al. 1 et 3 et 66 al. 1 LTF) et n'ont pas droit à des dépens (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Un émolument judiciaire de 1'800 fr. est mis à la charge des recourants.
3. Le présent arrêt est communiqué en copie au mandataire des recourants, au Service de la population et au Tribunal administratif du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 30 novembre 2007
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le président: Le greffier: