The first question is who is building it (and paying for it) and why? It will be the answers to those questions that answer many of the others.
There have been new steam locos built for commercial use (Disney, Mt Washington) and there is at least one long standing effort to build an early V&T loco.
As long as the loco isn’t much bigger than a D&RGW K there are a couple of shops which could Shepard the work. If larger you get into issues of cast frames and such which might be more difficult. The most qualified is probably the Strasburg Railroad in Pennsylvania, but there are several others that could do the work if you had the money.
The Strasburg has the assembled frame of the V&T Lyon on the shop floor as we speak. That effort used both traditional castings for the cylinders and drivers, as well as weldments for some parts including journal boxes, and machined parts in place of forgings. The boiler hasn’t yet been sourced (as far as I can tell) but was to be a welded unit last I heard. Of course all work is subject to the same regulations and inspections that any tourist railroad equipment would be (and might vary based on where you wanted to use the loco, you may or may not need a FRA sign-off)
The cost is again subject to many other factors…
How large a loco (steel and castings have a price per lb, so a 20 ton shay will cost less than a 40 ton 2-6-0 (but not half, there are lots of costs which do not scale))
How quickly do you want it. If you expect the shop(s) you are using to drop everything it costs more than if you let them put if off until the off season.
How good a project manager are you? A good manager can save money, a poor one can waste money.
How flexible is the design. If you are trying to build a museum quality replica you will spend more than if you are willing to adapt to modern technology or available parts as needed.
I have heard costs (from sources who I trust, and have loco experience) for a small loco (8-10 tons) as low as $150,000, and for a medium loco (say a large narrow gauge 2-6-0) of well over a million, to several times that (how fast do you need it?).