What you are looking for is Fractal Noise generation algorithms, the most popular of which being Perlin noise with successive octave noise generation (in addition to simplex noise, which is patented by Nokia, however the patent expires in a 2021 and if you want to take the risk, technically doesn't apply to terrain generation (only that which "generates an image")).
I'm not going too in-depth into perlin noise here, but I'll give a rough overview to how it is really the closest thing that solves your problem.
Perlin noise is a type of Gradient Noise algorithm, which smooths out visual artifacts compared to Value Noise. Both of these types of fractal noise generation techniques work via pseudo random hashing of grid coordinates which then create a pseudo random value at that grid point implicitly, which can be independently accessed and repeatedly generated with the same value regardless of the existence of values around the point. All these techniques need to know is the index you are trying to generate, and how many octaves you want to generate on top of it. Values at each point are interpolated between each value that corresponds to grid intersections, this creates noise.
Octaves are what create the fractal, correlated patterns you see in the wiki articles (the cloudy images). Octaves are successive application of the same algorithm but summed up with some weight applied to each level. You start out with a very high frequency octave (which is to say, high resolution grid, acting as if the discrete points you generate are actually several sub points within that grid, higher resolution means the less points correspond to a single cell of the grid) and succesively sum up lower frequency versions of that grid until you get what would look like the images above.
These values end up just being numbers, so they can map to anything you like, people often use this to generate terrain quickly.
Value noise just means at each octave, or run of the algorithm, you act like the corner point number you've generated with a hash is just a value (integer, float or otherwise). In Gradient noise, this value becomes a direction, you will end up generating hills which give you values based on their height, interpolating where you are on the hill based on the directions at each point. This creates a Gaussian smoothing effect of features, in addition to creating less directional artifacts visible by people on successive octave generations.
These techniques are not limited to 2D or even 3D, this type of generation can be used to create moving 3D clouds by using 4D noise generation, where the 4th dimension is the time location instead of a spacial index location. These techniques can work on Ndimensional data (but are obviously slower at higher dimensions)
Again, you can generate any point independently from any other with these methods, there is no interdependence on adjacent values.
Now how would you use this to generate like you say?:
terrain with biomes, trees, caves, ore deposits and structures like villages.
I am unsure of the specifics on minecraft, but I do know Notch says that the game uses perlin noise generation.
For 3D height maps this is easy. You can easily generate hills and mountains with this using the output value from summed octaves as the height you want, and this can all be done with 2D perlin noise.
If you want different physical characteristics of the noise (like sharp spine ridges or more bubbly appearances) you can modify your output, or change your indexing formula to warp space and create such characterstics. See here for visual examples of what gradient noise is capable of
Caves on the other hand are a bit tricky. Have you even wondered why minecraft has floating islands? Well part of the reason it exists is likely how horizontal concave terrain generation is handled, for example what is required to create caves and cliffs.
One way to handle this is to use 3D noise generation and the 2D surface generation together, and only fill in blocks that exist within the 2D initial surface and pass the "empty" threshold value that you will use to interpret the 3D noise output with. The issue with this approach is that, in some instances, this will produce the artifacts you see in minecraft. Floating islands can happen in part because the "floating" part may have passed the threshold, and despite the empty part being inside the initial 2D surface, it didn't pass the threshold and was left empty.
This can be partially mitigated with out block interdependence via using the height map value you are generating at to also determine the empty threshold (making it harder to be an empty block the further up you are generating at). However, with out some block dependent post processing fix up this is usually not completely fixable.
The good news is that from this point, if you understood how to do the previous stuff, the rest is pretty easy. For deposits, like combining 3D and 2D to create caves with height maps, we can simply apply another perlin noise function to figure out whether or not to place a deposit and what type of deposit it should be. Biomes can be handled similarly, either with a single noise function, or multiple functions that produce different biomes based on overlapping values, in addition to incorporating elevation. Trees can be handled similarly, with another noise function which simply places the tree on the surface generated as the height map is generated and biome calculated. Villages will be a bit harder, but in general you can at least place the spawn place of a village in a similar way. You may have to move away from block independence to create a logical structure, something like cellular automata may work. Village place is spawned, and then generated outwards from that location later. But of course you may be able to find a way to independently generate it with via perlin noise like everything else, the issue is how to generate the structures themselves, one compromise is using predefined structures, and connecting them online, or even having entire predefined villages.
For an additional resource awesome redblog article goes over tree and biome generation in this style but in 2D and with actual code.
