Though you could argue about the story part... Chess doesn't have one, for example, neither does Formula 1 and 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.