I have never tried a bicycle wheel, but I have rebuilt a motorcycle wheel with new spokes and got it within 1mm of true, which was half the factory tolerance. The wheel stayed true for at least 10,000 miles of hard use. A couple of observations which might be of interest:
1. In an ideal world with perfect materials, all spokes on a true wheel would be of precisely the same tension and emit the same note when plucked. However, there will be variations in the composition of the rim and spokes which means that you will rarely or never achieve that. I aim for all spokes giving a similar sound (say within a perfect fourth, for the musicians among you) and would always tighten any that went plunk rather than ping until they were musical. After that, it's more important to get the rim true than to chase any theoretical perfection in the spoke tension.
2. If you are going to fit all new spokes or a new rim, take a photograph, or several, of the old wheel, showing the angles of the spokes, where they cross, how many they cross, and whether it is over or under. Once you get the wheel dismantled, you will never get it back again the same way unless you have a record of the layout, and a photo is the quickest way to do this.
As someone said up there ^^^ it's not difficult to get it nearly right, and very satisfying to do so, provided you are methodical. Frozen nipples are the main enemy (ooh, matron) and a good practice is to dip the thread of each spoke in engine oil before fitting, and then give each spoke a slight turn (say one-eighth) and back every season to keep them free. Always check the inside of the rim for protruding spokes and file back, as they can be very sharp.