So, like we did for Pirates, let's list all things Viking, and see what use they could serve in a game, beyond theme:
Dragon-headed longboats beaching silently out of the mist
Pointy-horned helmets and round shields
Fur vests and strappy sandals
Beards
Norse mythology
Hordes of dauntless marauders
Berserkers
Pillaging and Burning towns
Building great halls to hold celerations and feasts
long epics and sagas
How about exploration? The Vikings discovered Iceland, Greenland, and North America (well, it was new to them anyway). That could add a lot of flavor to a game, especially if the areas on the other side of the ocean were random (and possibly included the edge of the world).
I also like the idea of a game role for sagas -- maybe your victory points are based not just on what you do (pillage, explore, etc.) but on how well your skald sings about it.
The original intent I had for allowing other players to raid each other wasn't to substitute the goods pillaged from villages, but to prevent said player from getting their loot home. More of a defenseive attack rather than an offensive one.
I LIKE the glory idea. I could go back to the old Beowulf title "Gold-Giver" and allow glory to be built up at the end of each return, after all your vikings have been paid. The excess gold is converted into Glory points. You could also use your gold to purchase Scops/Bards. This would cost quite a bit, but it would allow a steady return of gold rather than a lump sum.
I want to add in the aspect of Runes and random events. I could see a Fate deck with special effects listed on them such as "Caught in a storm" that halves a player's movement, or "Berserker" which adds 1 to your combat rolls for the remainder of the season.
Villages and towns will definately be scattered and random. My idea for this was to have each player place a single village at the begining of the game. Then, each round the players may either place a new village or upgrade an existing village. This causes them to strategically place the bigger towns farther away as long as they plan on buying that bigger ship. If a character decides to use smaller ships primarily, then they would place small towns closer to their home. This runs the risk of having larger raid parties come through and sack it before they get to it.
"Hey guys, we're out of mead..."
"We are almost home."
"Hey, there's a village. Let's plunder that on the way. We can restock our drink and take some fine, young slaves!"