Could the BGE handle procedurally/random generated terrain?
I.e. for example some zones would be hand-crafted, but between them would be randomly generated terrain. I.e what im looking for is to make distance seem realistic, for example instead of having a constrained “level” with invisible walls or a huge hand-crafted map spliced into sectors.
So could BGE handle this without too much slowdown?
The BGE is not designed to create meshes on the fly. Maybe it is possible with the new dynamic loading. You might look for such threads.
Blender do create game object on the fly when You load blend file including dynamic loading with libload. But we do lack a api to (in a sane manner) generate new meshes at runtime 
The only option is to create new mesh object in blend file format as a string and then load them with libload - python is powerful enough for that but it’s quite insane.
The best practical option is probably to build the terrain by combining a set of pre-made pieces.
Procedural data can be made before hand and loaded into the game later. As far as i know procedural generation in-game is nothing to shake a stick at.
The easiest way in my opinion is what LaH suggested. Create land chunks between handmade chunks using something like a random offset tool and constrain to to the up and down z axis. Then write or have someone else right a small script that loads these chunks as they come within view distance.
I’ve been working on procedural generation within the game-engine but right now its far to slow to be of any major use. So above is the best way i can think of to do what your asking to do. Monster is right though no new meshes can be made while the BGE is running unless it is made externally and import it into the game, as LaH mentioned is really messy i wouldn’t suggest it either.
I guess you could load a flat mesh (with enough details) and move the vertices around. That would be quite easy to do.
If you have multiple of them you could get your procedural mesh. Unfortunatly I do not think you can change the texture (except the UV).
Ok thanks guys, that pretty much answers my questions.