Though it may be difficult, I think it could be done. And removing land wouldn't be too difficult. You can just use an alter map function to replace some of the solid tiles with blank tiles. Checking the speed of each lemming on impact with the ground could be done with script. Though I never played the game much, I'm pretty sure you couldn't hit the ground to hard...
Um... what else...
Okay. Did a little Wikipedia research. The blocker (a la Durnurd's avatar) could be done through collisions. Builders could operate through an alter map function, and the same for the miners, bashers, and diggers. Climbers could be set to follow right wall, and when it's detected that there's no solid except above them, they can be set to a falling sprite and then to a follow left wall sprite. Bomber, well, alter map and some flashy animations. The little umbrella guys could just be set to zero gravity and a vector movement downward.