Make a 2x1 column of cobblestone. Stand in the middle of the 2 and build up whilst mining the ceiling. If you hit lava hurry and place blocks to get rid of it and find a different direction to build up. It's dangerous but it will get you to the surface.
Why the hell didn't I think of this long, long ago. I'm always getting lost.
That sounds like a job for the sniffer dogs... Sick 'em boi!