Minecraft Pi Edition is a free, cut-down version of the Pocket Edition, and contains only the creative mode. The thing that makes it such a useful tool to teach programming is that they have released a set of Python APIs for it, which means you can querry and manipulate the world programmatically!
The coolest examples I've seen so far come from Martin O'Hanlon, the author of the MagPi article. I used his "Hide and Seek" game at the Maker Faire. It hides a diamond block near the player and give clues if they are getting warmer or colder. His website is an excellent starting point for getting it installed and doing some basic examples.
The best application I could come up with, since I get so turned around, even in a 256 x 256 world, is an interactive map. I wrote a Python script that scours the surface to determine block types and constucts a map. You can then plot the player positon on a map using PyGame! It has two drawbacks. First, my algorythm to detect the surface is pretty inefficent, taking hours to complete. Secondly, the ineractive part only tracks the player, and not any building or mining you do. Lots of room for tweaking there.
At the Faire, the kids were mainly interested in playing, and quickly lost interest in the Hide and Seek game. I am still looking for a good way to get them interested in programming, so I think I will have to come up with something to limit their free play. I'm thinking of having them determining how to place blocks to spell their name or build a small room.
Give it a try, but be careful. Both Minecraft and Python can be addictive!