"Another World" is Eric Chahi's Amiga masterpiece from 1991 about a scientist who is transported to a world in a parallel dimension, when an experiment with a particle accelerator goes wrong.
I just saw the start of a play-through on youtube and it's still mesmerizing almost 20 years after it was originally released.
One of the lessons learned from that game is that story doesn't mean dialogue - there isn't one line of (English) dialogue and still you have a very strong sense of story.
Which brings me to one of my favorite discussion topics:
If you put a character in a game and this character has a goal, then you have a story whether you like it or not. Even if this goal is finding out what is going on or just escaping the place - the game has a story. It doesn't have anything to do with dialogue or written text.
You can't escape the story in this type of games ... but you can have a bad story. Eric Chahi had a very clear idea of what story he wanted to tell, even if there's no dialogue or written explanation in the game.
However: if you say that your game needs no story - it's just "Space Marine on Mars something-something with monsters" - then you actually have a story; a bad story.
"Tetris" hasn't got a story - a lot of puzzle games of that type doesn't have or need a story. But there's a lot of games out there with bad stories - and I suspect that the stories in many cases are bad, because the developers didn't think their game needed one.
So ... if you're doing a character driven game, your game will have a story no matter what you want. What you can do is make sure it isn't a bad story.