Though you could argue about the story part... Chess doesn't have one, for example, neither does Formula 1and Doom was the mother of all FPS without it as well.
Of course a good story can help to create a context for an action game and add weight and emotional impact; and RPGs, RTS games and such absolutely need one, too. It depends...
Doom had a story and a pretty original one for it's time.