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.