Storylessness gaming is the hallmark of the early arcade generation, which people still follow in the hardcore community, and the examples from that era are endless.
People have spoken about puzzle games, so here's another few examples.
Sports games are mostly without story, since they centre around the game itself rather than the men on the field and their conflicts.
Chess (which has plenty of video game iterations) is also storyless. While you might say that plenty of stories have been born of chess, I would argue that this is merely a consequence of the game having no larger meaning. Metaphor states that each piece is a part of a feudal system of royalty and religious power, but these characters have no names or inert purpose until you yourself assign them in a feat of invention.
This feat of invention, like with most video games, is what takes away an author's or developer's control over the outcome and takes away a story. When the control of the original creator is lost and given to the player, story disappears, with pure gaming in its stead. (Though, quite frankly, I don't think "pure gaming" is at all superior to storied gaming, I have been known to like both.)
Eldritch Warlord said:
Quake has a setting (a sci-fi setting featuring a war with aliens from what I understand), a character (yourself), and a plot (the things that you do). Therefore it has a story.
I'm sorry, but I speak with my writing major almost complete. I must say that that's the bare bones of a story, not an actual living or functioning one. The sausage with mustard and sauce does not a hot dog make. You still need the bread.
To speak more literally, so far as my more strict guideline is concerned, a plot has to function, i.e. have controlled development, to have a story. Ergo, a game with no written intro, no cinematics, no specifically assigned story quests and has highly open controls (like open environment and sandbox games) is storyless. In the other direction, the more linear and controlled a game, the more story-like its plot becomes.