Specifically, is it possible to generate a 3D mesh/terrain that is capable of producing holes that can connect from one part of the mesh to another?
The BGE does not generate anything. It loads all mesh data from .blend.
Therefore you can generate your mesh within Blender save it inside the blend and load it from there.
This is pretty static (a fixed number of meshes). There are various methods to hide this limitation:
combine different "patches" to build an object with variations (Example: puzzle, grid tiles). This works with any structural design and can have any detail (from large patches to very tiny ones). It is important that patches fit together.
manipulate the mesh vertices in-game to get variations of the same mesh (Example: terrain as height-map. This does not match your requirements as it is not possible to create bridges and loops.). The basic idea is to ensure the mesh does not look exactly the same as the original. Therefore the limited number of available mesh-"types" is not noticeable that easy.
Both methods can be combined. E.g. you can have an height-map mesh but add bridges and loops as patches on top of it.