Here, try some infinite maps
There’s a lot of bugs and a lot of missing features, but here, have some infinite maps:
http://www.minecraft.net/infdev/index.jsp
_please_ don’t report bugs in this yet, I am aware that it’s extremely buggy.
From my highly scientific experiments, I think depth of 256 should be enough for almost all purposes (that’s the same depth as a deep map), but this version is only depth 128.
Making a fast and interesting level generator for this is going to be very fun, I’m really looking forward to it.