Well, "folklore" is a very broad concept. Since "Not of the Eddas" still leaves quite a few important sources which I don't think were intended to be included, I'll briefly list them and move on:
- Saxo's Gesta Danorum, which contains independent retellings, but which seldom is used in interpretations, particularly non-scholarly ones.
- Scaldic poetry not actually part of Snorri's Edda, or the collection known as The Poetic Edda.
- Snorri's Heimskringla, in particular the first parts of the Ynglingasaga.
Beyond this, there are other important sources but which does not relate to stories as much as things like cultic practice.
Anyway, on to actual stories:
The Wild hunt
The most well-known and varied story is probably that of the Wild hunt. The general myth appears all over Europe, with several different figures as leaders of the hunt, but in Scandinavia (as well as in souther Germany and Switzerland), it is lead by Odin. In Germany, it also appears to sometimes to be lead by Frigg or Freya.
Odin's last battle
While I could techinally exclude this on the grounds that it is actually older then Snorri's Edda, it is roughly contemporary with the story it tells, so I will include it:
In the Bagler Sagas, which mostly deals with Norwegian civil wars 1202-1217, there is an episode where Odin appears to a blacksmith and explains that while he has been busy in Norway for a while, he will now leave for Sweden. Four days after this stood The battle of Lena, in which Eric Knutsson of Sweden defeated the disposed king Sverker the older, who sought to return with Danish aid.
Loka Táttur is an interesting piece: a medieval Faroese ballad, it tells a story of how a farmer lost a bet with the giant Skrymir, who demanded his son as payment. The farmer asked three gods for help: first Odin, then Hœnir, and finally Loki. The first two manage to barely keep the boy safe for a day by hiding him first as an ax in a field of crop, and then as a feather on the head of a swan, but the giant almost get to him. Loki, in turn, hide him in the roe of a flounder. The giant catches this flounder, but Loki has prepared a trap, and manages to kill the giant and return the boy to his father.
Odin, aiding and abetting
Well, this is kind of borderline, but I include it because I find it interesting. In October 1484 in Stockholm, a thief named Ragvald "Odinskarl" confessed that he for several years had been forsworn to Odin, who had helped him to break into and steal for churches. Ragnvald was executed.
Thor, slayer of giants
Again, not much of a story here, but some mythological remnants of Thor collected in Sweden: first, that thunder and lightning were for a long, long time connected with Thor, and second, a belief that giants and trolls were once real, but that they had all been killed by Thor.
Freya, maker of mischief
This is a folk belief from Småland in Sweden: according to it, during the night before Christmas day (generally a dangerous night according to folk belief), Freya would cause mischief: she would shake the fruit trees, and if a farmer had forgotten his plow or harrow outside, she would sit on it and make it useless.
- The story of Odin and the blacksmith, before the battle of Lena, can be found in Till 1700-årsminnet af slaget vid Lena in Fornvännen by Frits Läffler (1908)
- Loka Tattir can be found in Faroese and with English translation here.
- The ideas about Thor I found in Swedish Wikipedia, in turn citing Folklorist Ebbe Schön.
- For the story of Ragvald Odinskarl, here is an online source quoting the original source with an English translation.
- The story of Freya I found in Britt-Mari Näsströ, Nordiska gudinnor