My four steps to (near) success:
1. Get throwing to Legendary. This is absurdly easy. My method is to find a spot with only one rock (where pressing 'g' automatically picks it up), pick up enough rocks to go down to about 400 or so (which is ok, usually; just outside of/in towns you'll almost never/never get attacked), then press t/t/Enter repeatedly until I either over-exert myself (where I dabble in step 2 some while I wait for my tiredness to go away) or run out of rocks, at which point I look to see about how many more rocks I have left to throw, pick up more, and proceed to finish getting it up this high.
2. Get ambushing to level 24 (aka x/2500 on the skills page). This is even easier than throwing, but a lot more tedious due to needing to walk a bunch and thirst getting in the way of constant training. The reason I say "level 24" instead of "Legendary" is because getting it to just legendary skill still leaves you with a 33% speed penalty while sneaking, whereas level 24 allows you to sneak with no penalty at all. Although it does take around 10000 more steps to achieve level 24 after level 19 (x/2000), so you may not want to do this.
3. Get wrestling to Legendary, or at least very high. This is the easiest skill involving enemies to train as long as you pick the right opponents. Zombies as mentioned are ideal, warthogs and deer will suffice (also as mentioned). Do not try wrestling scorpions; they will pwn you given half a chance (my latest game learned this the hard way). Elephant/hippo/unicorn wrestling is likely bad for your health as well.
4. With three Legendary stats, you'll probably have gotten something like Ultra-Mighty, Unbelievably Agile, and Superhumanly Tough or otherwise for stats, but you still need one last thing before you can seriously think of emptying a ruin/cave/dark fortress/etc.: armor. No, your armor is not going to be good enough. Even if it's all iron to start, it won't provide enough protection for the bigger nasties (things like snakemen and antmen, yes; things like cyclops or colossi, not so much). If you're an elf, you're kinda borked on this point (elves can't wear metal IIRC), and dwarves will have to either find dwarf cities or be pretty damn lucky with dwarf fortress ruins (AFAIR they can't wear the stuff humans make). If you're a human, however, this point can be addressed by finding a ruin, turning on your stealth mode, and looting as much treasure as you can snag and/or carry without being caught and slain by the zombies and skellies. Given that they've all got places to be, it's pretty easy to loot the whole place if you're patient and careful enough, and all that loot will allow you to buy several pieces of exceptional equipment (masterpiece armor, as opposed to masterfully designed armor, is unfortunately difficult to come by in the human world :/). Things you should go for are head protection (helms IIRC are the armor bit) and chest protection (you can wear about three layers of chainmail), as well as arm and leg stuff so things that will try to bite and tear off chunks of your fleshy bits won't manage to get anywhere. Also go for iron whenever possible, as that's the strongest of the three materials (iron, bronze, and copper). Also also, if you don't have the dough for something nice after several purchases, make another trip to the ruins and collect the crap the zombies/skellies are wearing (preferably the ones that aren't too banged up, but you can probably sell the XX stuff as well if you want). Once you have replaced a fair amount of your armor with exceptional or at least superior stuff, you can probably safely clear a cave. While shopping, do not forget to look before you buy, especially if the item appears to have a design on it; whatever the highest level of work is on the item appears as the overall level of the item, regardless of whether it's a design or the item itself.
My usual build for new chars is: Talented (Weapon User), Talented Armor User, and Novice Wrestling.
[ July 23, 2007: Message edited by: BDR ]