As mentioned in the comments, a challenge was posted contesting the content of this answer. I answered the challenge with multiple real-world usages and the alleged origins of the expression. I'm linking it here as it serves as a further elaboration of this answer.
I want to add a counteranswer here, not because I think Sean's answer is wrong, but because it's a literary device used more broadly than just in Korean folklore.
To that end, there needn't be a reference to tigers smoking. Some cultural usages cannot be traced other than noting them coming into use. I cannot find any explicit reference on the origins of the Korean tiger-smoking phrase.
In (Flemish) Dutch, a similar turn of phrase is used, translating to "back when animals still spoke".
I don't quite agree that there should be a specific reference, or that facts about the introduction of tobacco are relevant to the literary device itself. The Dutch variant makes it clearer that the intention is not to point to a factually accurate period in the past, but rather to paint the picture of a completely different world which has no relation to the one we (the narrator and reader/listener) are in, so the reader/listener doesn't bother trying to find connections that aren't there.
Similarly, observe the well known Star Wars intro:
This loosely translated to "The following story is entirely unrelated to our current world, don't bother looking for connections to it." It encapsulates the story in a world of its own and suggests to the viewer that it should be viewed as such.
One of the main reasons that Star Wars needed to do so is because there is a race of humans, but they are not the humans who once lived on Earth. There is no Earth, there is no reason to think that there is a backstory related to Earth or human origins, and it needs to be made clear to the viewer that this line of thinking is not relevant to follow the story.
In all mentioned cases (Korean, Dutch, Star Wars), the intention is to very quickly get the reader/listener to stop looking for real-world references and instead focus on the story at hand, since this world/time period is clearly not our own.
Comparatively, "once upon a time" is much less explicit about there being no real-world connections. It doesn't actually restrict the possibility that we're telling a story that is grounded in the real world, though it is generally inferred to introduce a story that isn't.