in a perpetual free for all arena

You can have events(and thus some lore) happen in the arena every now and then.

I am making a game that involves player killing each other in a perpetual free for all arena. Its still open whether it will be sci-fi or fantasy.

Can this kind of game have a good story? Or is it doomed to have a shallow plot like "Quake 3 Arena" and various other tournament themed shooters?

What a silly question, of course it can! You can give the meeting of a dog and a squirrel an epic storyline, the thing is you don't really need it. The reason Quake 3 Arena had a shallow plot was because it had one at all. It doesn't need it because that's really not important, it's not what drags you in the game and why you play it for, it was more or less a more-or-even-less-plausible-excuse-to-kill-people.

However you COULD add some little context to the world around, such as a bit of a background/new setting.. like a slave caught by an alien race made to fight to the death for the honor of... blah blah... green-ugly-toad-king-thinggye, in the great arena of blah-blah-blah-copyrightinfrigment-the-hut.. And you can ad some atmosphere by using mascot characters, or even announcers/commentators, and you can get away by sending some background story of them in the lore-button thinggy.