You would appear to have a high resistance section somewhere - when you say half a circuit, do you mean:
As to which side is high-resistance (hot or neutral) what voltage to you see when measuring from hot to ground and turning on a switch or plugging in an item? In the unswitched state it should be the same 118V (or so) as hot to neutral. If it remains at 118V (H-G) when you flip or plug and something goes dead, you have a high resistance on the neutral side. If it goes dead (H-G) the high resistance is on the hot side. In either case you don't have an open circuit, since you DO have voltage when nothing is on - you just have very little current available, because something is just barely connected, or a wire is mostly chewed through, or something like that.
To the extent that you can infer (or know) the layout of the circuit, the problem is between the last working item and the first non-working item. You can use various methods to track it down - turn off everything, turn off the breaker, use your multimeter to check resistance between hot and ground while running around with a low-resistance load like a heater or incandescent light and plugging it into various outlets (circuit breaker off, remember!) If the load reads as (say) 5 ohms (on its plug) you will see something very close to 5 ohms when plugged into outlets well-connected to the outlet you are reading at, and some much higher number when plugged into outlets across the problem area. Eventually you may be able to isolate to a particular cable, at which point you can pull the outlets, disconnect the cable, wire-nut black and white at one end and read resistance at the other end.
You may, ultimately, have to rip open some walls to follow the problem cable and find the problem. You should not have to "replace every wire in the circuit" or anything like that. If ripping the walls open is a big problem, you may be able to disconnect the bad cable section and run new wire up or down the wall without making new holes in the face of the wall to run a new cable in the basement or attic to bypass the bad cable.
But you may, by careful checking this way, find a bad connection you have somehow missed, rather than a bad cable. Be open to either possibility, and work to isolate where it must be, whichever one it is, from both the working and non-working parts of the circuit.
You may also want to try using your NOSE as much as you can - the flickering you report happening earlier was probably associated with some arcing - there is likely to be some burnt material at the location of the problem. If you smell burnt insulation anywhere, you're close, probably. If anything was nailed or screwed into the walls about the time the problem started, look there. Otherwise you may be hunting rodent damage, and that probably will take opening up the walls to find.