Everything except first one is a common beginning of fairy tales (as well as "Once upon a time"). When you introduce multiple people, you say "Жили-были", when you introduce one man, you say "Жил да был" (or "Жила-была"). When you don't introduce anyone, you say "Давным-давно" (which, basically, means "Once upon a time").

First is an introduction for a strory (not a fairy tale, just a story) that basically says that something happened in the past.