I have spawned in many strange places, including inside trees and underwater. If you were playing during alpha and beta, you would have most likely run into gravel beaches a few times when creating a world.
I spawned in the rock wall of a cave. Yes, not just in the cave itself, but in a wall in the cave. I remember that it was recent because I had to switch to creative to keep myself from dying and to break out.