Magma men leave a chunk of obsidian upon their death. Of course, killing them bare-handed is pretty hard, but ancient dwarves could use some clever techniques like luring them all the way through a cave to the surface and in a herd of zombie elephants. (Or, more easily, through a tent to the circus and in a crowd of clowns.) This may be the hypothetical first block which was used to build first kiln which was used to collect first clay which was used to build more workshops which were used by moody dwarves to make first bone anvil and first bone pick. Problem solved?
well, yes, although that seems overly complicated. i mean, if you have a boulder, you wouldn't need to build a kiln to get a boulder to make a workshop, because you would already have a boulder. although i suppose that would certainly provide for them to have made multiple workshops much more easily than other ways.
so, what are we up to so far? dorf kills a magma man (somehow), uses that to craft a kiln - make that a magma kiln actually - (so that they can get many boulders instead of just one), uses the kiln to get clay boulders, uses the clay boulders to make one or more workshops, specifically including a craftsdwarf workshop, uses the craftsdwarf workshop to mood a pick out of bone (which will have to be butchered to get, i suppose, so now we're up to a craftsdwarf shop and a butcher's shop, requiring only some sort of tame or killed animal. maybe we should add a bowyer's workshop to make it easier to get more bone?).
additionally, a magma smelter will be necessary (we still don't have a source of fuel, although eventually you're bound to mood out a regular axe as well, possibly before even the pick), which does not require an anvil. perhaps at this point, the first anvil was not, in fact, a rock, but was actually a metal bar. or even a pile of metal bars, all stacked up.
perhaps the first anvil was actually a gigantic structure (shaped like an anvil of course) made using metal bars, which can in fact be obtained without an anvil. at this point, you would need some sort of giant blacksmith (presumably armok, unless titans can learn crafting skills - which seems unlikely... i've never heard of a titan with a beard) to come along and forge more dwarf-sized anvils.