Truly violent gives a lot of room for maneuver I'd think. Doom is the logical candidate, but I had played plenty of games before doom that had me killing things. Alien 3 on the SNES maybe? Earlier than that there was Operation Wolf - a standup arcade game (also an NES game) that was an early precursor to the rail shooter (the screen pans side to side and you were given an Uzi to blast people with. You not only had limited health per usual, you also had limited ammunition and could lose if you ran out of bullets)
There were games even eariler than that that involved me shooting people (CABAL for example) but the violence was so . . . cartoonish (or videogameish?) that I don't know if I can call it "truly violent". The first video game I played that involved killing something was Castle - a "graphic" adventure game that presented the entire world using the ASCII character set (including system characters). That I killed an ogre with a sword may seem violent, but considering that the graphical depiction of the occurance was ☺ɸ makes it fairly tame.
Doom was the first undeniably violent game that I played, but it was not until I played AVP (PC) that I realized just how magically violent a game could be. Soldier of Fortune took that bloodshed to a whole new level of fidelity, which was furthered by SoF 2. I have yet to play a game since SOF 2 that has actually tried so hard to be ultra-violent. In fact, most games these days simply spray a bit of blood, the body drops and soon disappears. Fear is the only notable recent example where one can still decapitate common foes with a shotgun.