I would favor a balanced coil metal detector, as you get both amplitude and phase to aid in discrimination what is under the coils. Looks like dc42 has proven the concept.
So, dc42, you are sampling 8 times per cycle, over 1000 cycles? At the same 8 points in the cycle, or are you collecting slightly different times so as to result in 8000 samples per cycle?
Interesting.... this one would be simple to implement in an Arduino:
http://www.docstoc.com/docs/150574517/Matchless-Metal-Locator-(Detector)---By-Thomas-Scarborough-(Silicon-Chip---June-2002)-7S---Geotech