Well, depending on what you mean by tough metal, I have listed all the structurally useful elements, as well as any notes I could find on their extraction:
beryllium: Beryllium is the first really hard metal on there periodic table. It's found in beryl, which exists as both precious stones (e.g. emeralds) and non-precious forms. It is obtained by electrolysis of beryl, and is thus unobtainable to pre-electrical folks.
Magnesium: magnesium is found in dolomite, which is pretty common stuff, readily obtained on the surface. It is also found in the mineral magnesite. It is a light and reasonably hard metal, although it is obtained by electrolysis or displacement reaction with a more reactive metal. More reactive metals are obtained by electrolysis, so you can't get at it without electricity either way.
Aluminum: Aluminum is refined today with electricity. You can refine it other ways, but these are less efficient, and require things only a technological society would have. Aluminum was actually once more valuable than silver, and it takes lotsa juice to get the stuff. recycling one aluminum can saves enough electricity to run your TV for three hours.
Scandium: Scandium is the next "hard" metal. It's common is some stars, but for some reason, it's rare here on earth. It has excellent structural properties, especially in alloys. It's rarity, however, makes it a tough one to find. It is obtained by electrolysis of scandium chloride, but chlorine is unobtainable without electricity, so you're out on this one too. BTW, the first samples of pure scandium were produced in the thirties, so it's hard even for an industrial society to get the stuff.
Titanium: Titanium is similar in some ways to scandium, except that it is much more plentiful on earth. It's useful in aerospace applications, and makes killer bikes. It's most common ores are found in intrusions in quartz, so you can find evidence for it on the surface. Unfortunately, it's just as hard as scandium to prepare, with the added problem that it doesn't melt easily, and reacts with carbon at high temperatures, meaning you couldn't use a wood or charcoal fire to smelt it.
Chromium: Chromium is described as brittle, but very hard. It is useful in alloys with iron, among other things. It's also
really shiny. It appears to be commercially extracted by electric arc furnace, but it was discovered in 1797, so there might be another way. It would be dangerous for a pre-industrial society to deal with however, many of it's compounds are toxic.
Manganese: Manganese is obtained from pyrolusite MnO2, a mineral famous for its tendency to grow in patterns that mimic (I've personally been fooled) fossil ferns. It's rather unexciting stuff, quite a bit like iron. it's name comes from it's ore's magnetic properties, I don't think manganese itself is magnetic. The ore can be found on the surface, and given iron's similarity to manganese, as well as the similar chemical formulae of the ores (Fe2O3 and Fe02 IIRC, I think iron exhibits a +2 oxidation state but I'm not sure), I think it could be extracted by a pre-industrial society rather readily. a quick google confirms this. It's reduced from the oxide with carbon, just like iron. The only difficult in using the stuff, which goes great with iron to make some really hardcore alloys, is that it's rather rare. Here's one good metal for you.
Iron: Iron is easily extracted and turned into steel by pre-industrial societies, I believe it has been well-discussed.
Cobalt: Cobalt is rare, found in an ore called cobaltite. It has characteristically blue compounds, so finding the stuff isn't hard. I believe it's associated with iron ores, though I could just be making that up. The main problem is that it's found in small amounts, too small for a pre-industrial society to get at.
Nickel: Nickel is fairly rare on the surface, but it may in fact constitute large quantities of earth's core. Nickels, the coin, are about 25 percent nickel. Nickel compounds were known to the ancient world, but the pure metal wasn't official discovered until 1751. the ancient Chinese, apparently knew about it though. It makes stainless steel, so it is useful. I can't find any info on its extraction or ores, but apparently it's possible to pre-industrial societies.
Copper: Copper is easily extracted by a number of processes from various ores, and was done easily by pre-industrial societies. In addition, it occurs in nearly-pure nuggets naturally. Thus, the copper age. It's ease of manufacture is offset by it's weight and weakness.
Zinc: Zinc was discovered before they kept records of that kind of thing, so it's apparently available to pre-industrials. It's not great stuff on it's own, but alloys with copper to make brass.
Anything below the third period transition metals is really to rare to bother with, save for tin, silver and lead. Those aren't useful on there own to any great degree, though tin makes bronze when alloyed with copper.
Finding them isn't that hard in some cases. If you're going for copper, the stuff exists in pure form on occasion. Looking for intrusions of the ores would be a good way to start, as well as any minerals the ores are associated with.