The cars have to receive power from someplace. Wherever they are being energized, there is by definition a complete circuit to all cars being powered on that line. Likewise, wherever the cars are, there is going to be a large and reasonably well-defined impedance discontinuity on the power rail. So, as a first attempt, I'd look at some sort of reflectometry scheme. Wind a few turns of wire around the cable that feeds the third rail, inject a pulse train with Gold codes or something similar that lends itself to autocorrelation methods, and listen for echoes.
This requires a grand total of $0 in hardware to be added to the cars. If it's not enough -- e.g., if the points raised in Anechoic's post render it impractical to rely on passive reflections -- then it should be possible to add a small amount of hardware at the cars to act as an active transponder, injecting its own pulse train in response to carrier-current signals from the distribution point.
So now we need to connect two wires at each car, and mount a small box with some duct tape^W^W milspec fasteners. Not exactly rocket surgery.
