I'm not a historian, but I have some familiarity with the history of machining.

Among the earliest machining tools was the Bramah Press, the first known hydraulic press. The hydraulic press can be used to press pieces of metal into predetermined shapes based on the head. This can be used to accurately curve and fold metal; if you ever watch some videos of traditional blacksmithing you will see that in many cases, unless using a specially sized horn to hammer metal sheets against. The ability to repeatedly and accurately curve, corner, and fold metal was extremely important because it allowed the first standardized metal parts.

Being able to perform these operations makes it significantly easier to produce other standard machining tools, such as accurately sized boring tools (think the tip of the modern drill, with a crank on the back). These can be man powered or water powered and other developments sprang from these.

Pictures of different types of early presses : http://etc.usf.edu/clipart/keyword/bramah-press

IPENZ (New Zealand Engineers) article on early presses : https://www.ipenz.org.nz/heritage/conference/papers/Gibson_J.pdf

*edit - Realized I misread the question a little bit. The earliest tools, like the Bramah press don't require a huge amount of accuracy to make, they can be made with traditional hand-manufacturing processes. The most error sensitive part is the actual channel for water to provide pressure without leakage, which was later improved by better boring tools. The move to machining tools was based off of hand made tools like the press, that can be used to make more accurate machine tools but were themselves made by hand.

Essentially any machine can be built by hand. The reasons why machines are used on assembly lines is for speed or interchangeability of parts. That is, if a craftsman makes 100 rifle butts by hand, they will all be slightly different, and require tedious hand-fitting to fit the rifles. So if you make a machine that traces along an existing rifle butt (the pattern) to cut out new rifle butts, you've saved a lot of effort. Here is an example of such a machine, the Blanchard lathe from the 1820s. As you can see it is largely a work of carpentry and blacksmithing.

But if you are making a machine that will be essentially one-of-a-kind, then it doesn't matter how accurately you've made the parts, all that matters is that the parts fit each other. For example in a lathe you need the spindle to run true in the bearings, and if it does you will be able to make perfectly round parts. It doesn't matter what the exact diameter of the spindle is.

Another example of how hand machining works is with making surfaces flat. For this the traditional technique of scraping could be used to make surfaces flat to well within the needed tolerances. First three stone or glass reference surfaces are ground to each other with abrasives. This ensure that all of the surfaces will be perfectly flat. Then a part in need of flattening is placed against the surface coated with a layer of paint. The paint will reveal the high spots on the part, and then these can be scraped off with a hard scraper. The process continues until the part is perfect. As you can imagine this is a very tedious process and in fact the metal planer was one of the first machine tools and was used to make flat metal parts.

The only exception to this is with screw threads, where if you want to be able to make an accurate thread you really need another thread that has been cut to an acceptable tolerance. This is something that was achieved simply by making one thread very accurately by manual methods, and then using that to make many machine-cut threads. A good source on this subject is English and American Tool Builders.