What pack are you using?
If you have MFFS 3 (Calclavia's fork), you could simply use one force field to mine out a big vertical rectangle underground, and a caterpillar drive made from a couple of the field modulator things (or whatever they're called) to move the rig along.
You say you have frames... Does this mean you're in a pack with Redpower, or are you using some other mod for those? If the former, an IC2 Mining Laser in long-range mode in a Deployer facing upward or downward will break a vertical column of blocks. If you're in a more recent pack, you could use an Autonomous Activator from Thermal Expansion with a mining laser to the same effect.
Alternatively, if you have lots and lots of resources, you could make a movable wall of Applied Energistics transition planes, which are basically instant block breakers that automatically dump their output into your ME network. However, I'm not sure how much AE stuff likes being moved.
Its a custom one in singleplayer only so I can add whatever I want.
Currently I am liking the MFFS route so I'll add that. I also have RiM and Funky locomotion.
So with redstone (I also have project red) is there a way to say if the frame machine moved forward 1 block then move left 1 then back 1 then right 2 then forward 2 (etc so it just makes one huge consistent hole in the ground?) Can this be done easier with computer craft? Just be noted that I absolutely hate programming for ten minutes than setting up redstone for an hour and a half.