Random spawn for multiplayer Minecraft server

Yes, this is possible in Vanilla. Using /setworldspawn, we can force players to spawn in a particular location. From that location, we can use /spreadplayers to teleport them to a random location in the world.

Now, in order for /setworldspawn to behave like we want it to, the default gamemode for the server must be adventure. We'll work around this in a bit, don't worry, but in your server.properties file, set gamemode=2 (and while you're at it, enable-command-block=true)

Create an unreachable location (a bedrock box underground will work nicely). Now, pick one particular block inside that box, and use /setworldspawn. This will set the spawnpoint of the world to be at your feet. Whenever a player dies without setting a spawn point, and whenever a player joins the server for the first time, they will spawn at this location exactly.

Now, we want to set the gamemode of that player to survival, and use spreadplayers to teleport them (making sure the order is maintained). You can use a pair of command blocks on a clock (or using the new repeat mode in the 1.9 snapshots):

/gamemode 0 @a[x=X,y=Y,z=Z,r=2]
/spreadplayers X1 Y1 0 R1 false @a[x=X,y=Y,z=Z,r=2,m=0]

where X, Y, and Z correspond to the location of worldspawn, X1 and Y1 correspond to your desired center of the map, and R1 corresponds to the desired radius of the map.