PVP with separate bases could be interesting, especially if we have two teams starting from scratch in separate locations. The problem there is that we'd keep respawning at the center of the map if we died, since beds are unsafe with the current version, unless you have them close enough to the default spawn point to not cause the server to crash (later). (Right now on the world I play on, we simply do not make beds at all, so I have no idea how close they'd have to be to be safe)
The host or map makers could build a complex at the center of the map for the NPCs to live in, and either provide some initial building materials and/or metal for the players, or not provide anything and leave it up to them to forage for it (but then depending on what they run into, such as corruption instead of a forest, that may lead to a disparity that determines how the game goes), who would head off in opposite directions to build their bases and equipment.
The question is, would that NPC complex be destroyable, or neutral ground, since everyone has to be able to interact with the NPCs? What tactics would be forbidden, if any? Building your own NPC rooms to try to obtain NPCs?
4 players on two teams is one possibility, unless you wanted someone acting as an observer / GM (It probably wouldn't be necessary). I don't see more than two teams working well due to the 2d nature of Terraria and especially the limited number of players.
Two threads on the official forum about the problem with beds:
http://www.terrariaonline.com/threads/so-i-thought-beds-were-fixed.9203/http://www.terrariaonline.com/threads/terraria-server-crashes-upon-someone-connecting.5972/#post-114695(Hopefully it gets fixed in the 1.0.2 patch)