The most widespread opinion is that it was indeed the first Rabban Shimon ben Gamliel (father of Rabban Gamliel of Yavneh), and that the Romans killed him (along with R' Yishmael) during, or shortly after, the destruction of the Beis Hamikdash - i.e., around 3830 (70 CE). The chronology of the nesi'im, then, would be something like this:
- Rabban Gamliel Hazaken (d. around 3810 / 50 CE)
- Rabban Shimon ben Gamliel (martyred in 3830 / 70 CE)
- Rabban Yochanan ben Zakkai (acting nassi, d. around 3835 / 75 CE)
- Rabban Gamliel of Yavneh (d. around 3880 / 120 CE)
The problem with this is that all of the other eight of the Ten Martyrs were contemporaries of R' Gamliel of Yavneh or of his son, Rabban Shimon ben Gamliel II, and were killed during Hadrian's persecutions in the aftermath of Bar Kochba's revolt (in the 3890s / 130s CE). Accordingly, the usual explanation is that the liturgy (or actually, the midrash on which it's based) is historiosophical rather than historical: it puts these ten Sages together in order to make a point (about the terrible consequences of the sale of Yosef, and so that we should mourn them more deeply), but not to say that they actually lived at the same time.
However, R' Y.I. Halevi (Doros Harishonim) argues, based on various lines of evidence, that the first of the Ten Martyrs should in fact be R' Shimon ben HaSegan rather than R' Shimon ben Gamliel. (He claims that the substitution arose by misreading רשב"ג for רשבהס"ג.) The second, he says, is not R' Yishmael Kohen Gadol but rather his grandson, also named R' Yishmael, the colleague (and frequent disputant) of R' Akiva. This indeed then places all ten of these Sages in the same time period.
(R' Halevi does allow that Rabban Shimon ben Gamliel I didn't survive the siege of Jerusalem, since after all he was still alive at the beginning of the revolt - Josephus refers to him serving as nassi - yet Rabban Yochanan ben Zakkai didn't ask Vespasian to save his life. He claims, then, that either Rabban Shimon died a natural death, or that he was killed by one of the Zealot factions who were fighting each other for control of the city.)