How many polys does a MineCraft scene normally run to? I don't know if they already do this, but for my mobile game I run a depth pre-pass where I render depth only with a no-op shader to build a full depth buffer, which then means that all fragments behind the depth get discarded and you only run the fragment shader (the expensive part) for those pixels which are actually drawn.

This gives me good frame rates (30fps+) on a nexus 4 for reasonable detailed geometry (including large procedural terrain) whilst still being able to run various post-process effects (ssao, bloom).

It's possible that the minecraft scenes are that much more complex though.