How can I generate an "unlimited" world?

Normally, all terrain/world generators work in the way you described - they are able to produce vast (random-looking) worlds from a very limited input data (set of parameters).

So, you might want to put further constraints on your question.

If anything will work for you or if you are just begging to research - take a look at different focuses and approaches here.

As for randomness/deterministic I am not sure that you really talk about randomness here and it can be a bit confusing, I think you only want to be able to create a lot of variations. So you might want to drop that from your search terms.

Take a look also at procedural generation (especially 'see also' and 'external links').

Personally, I think there is a lot of promise in the concept of terrain synthesis where you basically mix and match real terrain samples with some sort of transforming operations - which provides realistically looking terrain with desired properties.

EDIT: Here's an implementation of 'plasma fractals' (mid-point displacement) in processing.

If that is good enough for you then you could rework the algorithm to allow it to generate any part of the grid (I have a feeling it will boil down to hashing the coordinates to get random number seed around connecting lines, or everywhere).

Also you might work with different levels of detail with this method so that you can generate more detail closer to the point of view.

Have a look at Perlin Noise, it is a type of deterministic random data named after it's inventor Ken Perlin. If you search for "Perlin Noise" or "Ken Perlin" you will find a ton of articles on procedural textures and landscape generation.