<p>I tried finding a python script in google that will generate a random terrain when the game starts (or each time a the player advances to a new scene) but all the tools I found are for creating a terrain to render it, not for the game mode.</p>

<p>Any idea how/where to find one?</p>

<p>(I'm assuming that since Blender3D has game programming capabilities, it is OK for someone to ask in SO)</p>

Is this link related?
http://blenderartists.org/forum/showthread.php?t=77794
To generate terrain (height map) the algorithm is pretty simple (fractal plasma), something like this algorithm (Java):
http://www.sinc.stonybrook.edu/stu/jseyster/plasma/
If you Google search for "fractal plasma python" you might find some example code.