While I'm thinking of a story line, I must say that I like the idea. The only thing is what happens next? What happens after they kill the north god? Just constant NPC killing for no reason? You shouldn't just give everything to the user all at once. There should be tens of thousands of hours of game play. Or at least thousands.. But anyway, just to get things clear, I kind of imagined you starting the game with a past story about the gods and a short (fast moving camera so it doesn't take a long time to zoom through the whole outskirts of the map) camera viewing of the land. I also imagined their being some islands for the western god, which would be where the west god stays. Oh, and the west god should have power of land, not of Earth.
Quick sketch of what I was thinking of
here.
Oh, and I like the shaking idea. I think that whenever a god is killed, the whole land will shake. The closer you are to the god which is killed, the more prominent the shaking is, and it will stun you or make you fall or confuse you or something (in the center, you won't hardly notice it; it will be something that new players won't really know what it is). And if you're fighting a god when another god dies, you'll see the god stop and look up in the direction of the god who died, and the god will then be in anger and be less accurate but stronger.
The point of this would make it a very collaborative game. If you wanted it to be less multiplayer at some points (how I imagine it, it would take hundreds of people to kill a single god at very high levels), you could have separate islands with demigods or something. Or Beta could be the mainland and you start out on some other big islands but they have demigods, or anything on their that can be fought by one or two people.
I have many more ideas if you wanna hear some.

And I'll be thinking of a powerful storyline.
One thing that you have to remember is that games like these shouldn't really have an "end." Not for a long long time, at least. There's still no end to RuneScape, WoW, or anything like that. In RuneScape there's still many gods that you have to learn about (bet you didn't know that there were like five or ten more gods that you've never heard of

), but I think they kinda trapped themselves in a corner with how they did it. But I do like the idea of having the four gods. I've never played a game like that, but it'd make me want to get more people involved, which is something you have to think about.
Hmm.. I was talking to my lovely girlfriend about this (she plays WoW (she's not ugly or anything by the way >_>)), and I got some more ideas, mainly relating to how you have the problem of it ending (which shouldn't happen for a long long time).
Alright, so my idea of the mainland is that when you start out, you're in the center of the land. All the god's are helping you (fertile soil (earth/land (I suggest land or something other than earth) god), water (water god), heat (fire god), and the ability to have fast growing crops and power (windmills) (wind/time god)), and the colors are bright and it's light outside and the setting causes people to infer that the gods are good (they are). However, as they wander farther away from the center (going south will give less wind and less time manipulation, going east will give you less water, etc., etc.), the setting will be darker and scarier, which will then make the player assume that the gods are dark and scary and evil, which will justify killing them. The reason things would be darker and scarier as you get closer to each god is because the demon that the gods are keeping at bay can't overpower your mind when you're in the center of the land (since all of the gods' powers are focused on one center point (main land)), but the demon can overpower your thoughts and interpretation of your setting when only two gods are helping you (south east would be a lot of fertile soil from the land god, and heat from the fire god).
After you kill a god, it gets darker still, and the demon makes things seem less happy and more like the gods are evil. After killing all three gods, all of the land will be scary and dead and you will be very powerful, and then the north god will seem much much scarier and evil than before. After killing the north god, you'll be given many other powers from the demon. If you still wanted to go the way of the dungeon, you could have the player enter the dungeon, and it's basically hell. There are many demigods, evil gods, etc., and the demon would basically be the north god of the good land (which you've killed). If you don't go the way of the dungeon, after you kill the north god, all of the land is filled with evil creatures and Satan-esque beings, and you realize that you've made a mistake etc. (I actually think that you'd have to go through a dungeon or fall through the land or be grabbed by the demon or something, since there will still be people in the main land).
The whole idea would be basically that you would be on the "good side" while killing the four gods (there should be more demigods and what not throughout the mainland, or on other islands/worlds/whatever you choose, to make the game able to expand later), and then you're on the "bad side" after killing them, and you have to kill everyone/thing on the bad side to reverse your mistakes and save the land by killing the demon.