Once in Hell, there is an Obsidian/Hellbrick city down there. Get into the lower levels of a structure, and you can mine safely. Hellstone is often pressed up against the walls.