To un-cheesily reach legendary skill, you'll need to know what kinds of enemies you can take on at certain skill levels.
If you start off below Competent in your weapon/melee skills, your best bet is hunting dangerous animals or wandering the wilderness for random encounters. Animals don't have combat skills, and they tend to scare easily, making them good for low-level training - but (being predators) they are not totally helpless, unlike livestock.
Once you're at Competent/Skilled, you can tackle humanoid bandits (most of whom seem to start with Competent weapon skill + Novice fighter/dodger/etc.). Do so cautiously: avoid multiple engagements, and watch out for their weapons - even if you have superior armor, a solid hit can still (thru force-transfer) bend or break your joints, leaving you crippled (temporarily or for good). You can tilt the odds in your favor by shooting bandits from stealth first. Just beware of flashing bandits, ones with decorated gear, or those called "[weapon]master" or "[weapon]lord" - they have higher skills.
At this level you may also be able to take on some young semimegabeasts - giants, ettins, cyclopes (not minotaurs, who are born with high melee skills). You want to tackle young ones because they won't have trained their skills in worldgen duels: look for beasts that have only a single name (meaning they haven't killed anyone), or at least not a title. Semimegabeasts (I believe) actually give you more XP than other creatures, and since they're huge they take many, many hits to bring down. You can gain several levels off a single ettin. Again, do this cautiously: one hit from a giant and you're basically pulp.
Once you've reached Talented you can deal with night trolls: I strongly recommend avoiding these at lower levels, as they tend to be highly naturally skilled fighters. Towns usually have a few in the sewers (who, due to a bug, teleport to the surface and start slaughtering people), or you can hunt their lairs in the wilderness. They have the questionable advantage of feeling no pain or fear, so they won't pass out or run away - which is good for training but can also, obviously, be dangerous.
Talented skills should also allow you to fight some megabeasts: dragons and rocs. Rocs are the easiest - they get scared about as easily as normal animals; they can fly away, however, so you'll need to damage their wings to keep them in range. Dragons are hard to get close to because of their fire - bring a shield - but once in range a skilled fighter should be able to defeat them.
Bronze colossi and hydras present additional difficulties. BCs are simply hard to damage, but if you can dodge/block their attacks reliably you should be able to fight one. I've never actually fought a hydra myself, but they have seven heads that can bite simultaneously, so again you'll need good defensive options (and a fair bit of endurance - dodging is tiresome)
You should also be able to face Titans at this level, but some are more dangerous than others. Avoid webbers entirely - once webbed you're totally helpless until you break free, which takes time. Fire breathers are bad, but not as bad as dragons. Deadly dust can throw you around and potentially knock you unconscious. But spittle, poisonous bites, bloodsucking, etc. are usually harmless.
All that should give you plenty to fight in a not-too-exploity way. Additionally, use your weapon's lamest attacks - pommel strikes or flat slaps for swords/axes, shaft bashes for spears or pikes, etc. They'll do (usually) less damage but still raise your skill, allowing you to prolong a fight, but be warned: the longer you stay in combat, the greater your chances of getting seriously wounded or killed. Even "easy" opponents can get lucky shots if you aren't careful.
Maybe fight tower zombies or something?
In the last version (.44.xx) zombies, for some reason, gave no XP gains. You could cut through an entire tower and gain nothing. Don't know about the current version, but I'd steer clear of zombies for training purposes until I verified this.