OK, I've officially had it.
Theatre Mode has been around for as long as there were Quake (yes, the original) recams. Quake was released in 1996, and the oldest recam I could find was the "Scourge Done Slick"-speedrun which was cammed July 26th 1998 [http://speeddemosarchive.com/quake/qdq/].
InGame levelediting has at least been done since October 3, 2006, when Ryzom Ring was released [http://en.wikipedia.org/wiki/Ryzom_Ring#Innovations]. Yes, levelediting in an MMORPG.
So, no cake for Forge either.
And as for FPS: Duke Nukem 3D had it, also InGame, if wikipedia is to be believed. [http://en.wikipedia.org/wiki/Duke_Nukem_3D#Multiplayer]
Coop has been around since at least Redneck Rampage in 1997 [http://en.wikipedia.org/wiki/Redneck_Rampage] in FPSes, and Split Screen since at least the original Super Mario Kart for the SNES (1992) [http://en.wikipedia.org/wiki/Super_Mario_Kart].
As for the weapons:
Flamethrower: Turok 2 / N64 (1998) [http://en.wikipedia.org/wiki/Turok_2:_Seeds_of_Evil]
Spartan Lazer thingy: DooM (original) with the BFG, somewhen back in the year dot.
Halo may have executed all this very well, but this ain't no innovation by whatever definition of the word, except when you define it as "Things that Halo 3 did somehow. Whenever, and no matter who did it first."
Hell, console gamers, get over the fact that the console manufacturers didn't give you online capability earlier...
Edit:
Killstats et al have been around since at least Quake 2, if not earlier.
Mark that I provided links with information everywhere. So you can check for yourself if you don't believe me.