Cheap 2D culling base / approach for 3D games with Camera's that mainly rotate over 1 Axis and Levels that primarily extend over 2 Axes. Extend to your own needs ..
@diki: For your specific game I'd add add a rule that culls everything more then let's say 4 steps away, unless a block is within 2 steps away over the X axis of the camera when facing east / west .. and over the Y axis ( Z in your game ) when facing north / south.