This has obviously been done multiple times by others, but I wanted to throw my hat into the ring and take part in this too. There may not be no set "story", but there is a lot of lore to interpret. Just a heads up, this still needs some ironing out so it may not be as good as I thought.
Villagers are Human
Villagers, the Squidward-looking pacifists that inhabit villages across the landscape, are an odd bunch. Besides the large nose and cranium, they look very human in appearance. I believe this is because Villagers are in fact a separate branch of Humans that have evolved differently. Some event caused Villagers to have a much larger brain and nose, yet they don't seem to be any smarter than your average Human.
Zombie Pigmen are an Extinct Race
The Nether is a strange realm that, even to this day, is still not fully understood. Like what the hell are Zombie Pigmen? I think that they may be an extinct race from the Overworld that existed way before Villagers and Humans. They were a primitive race that were and still are unusually greedy when it comes to gold. This "primitive race" idea stems from the fact that they wear nothing but a loincloth, carry around weapons and just relentlessly chase anyone who hurts them. Despite the ability to create tools from resources mined, they still run on instinct whenever they attack as one.
The Mystery of End Portals
Minecraft's strongholds are structures built by an unnamed society that learnt how to travel to The End. The End portal frame is odd, as the lower section comprises of Endstone which doesn't naturally occur in the Overworld. The simple answer would be Endermen tunneling through to the Overworld were carrying Endstone in hand, which was retrieved after killing them. How the unnamed society found out the way to travel to The End is still quite a mystery.
Welp, that's all I got for the time being! Thanks for reading.