So I take particle A and place it in space, then I place particle B 1,000,000 light years away from particle A.
But, just to be sure:
In astronomy, and (prehaps somewhat more recently) in cosmology and in physics in general, we understand this measure of "having been apart" as chronometric mutual separation. In your example this means specificly that
A and B should have conducted a trial which took A 4,000,000 years (at least) and which took B 4,000,000 years (at least) where
for (at least) each signal indication which A stated during the first 2,000,000 years of the trial A observed the corresponding echo indication of B exactly 2,000,000 years later, and
for (at least) each signal indication which B stated during the first 2,000,000 years of the trial B observed the corresponding echo indication of A exactly 2,000,000 years later, and
all durations of A which A calls "$t$ years" (for some real number $t$) and all durations of B which B calls "$t$ years" (for the same real number $t$) were confirmed equal by means of "our handy cosmic chronometeres" (Marzke-Wheeler clocks); see also MTW Box 16.4. The region containing A and B may be thought of as being (sufficiently densely) filled with such Marzke-Wheeler clocks.
I strike a line between the two, and measure that line as having a length of 1,000,000 light years.
Do you mean that additional particles would have to be found, throughout the trial(s) by A and B described above,
namely one particle P for each real number $0 \lt p \lt 1.000.000$, such that
P was and remained "placed $p$ light years away from particle A", and
P was and remained "placed $(1.000.000 - p)$ light years away from particle B"
Well, if that's your requirement for your setup prescription, so be it.
But, just to be sure:
That's not necessarily required for plainly attributing to A and B some particular value of (their) chronometric mutual separation; such as "1,000,000 light years".
I verify this measure by taking out my handy cosmic calipers [... or tape measure] and confirm that there is precisely 1,000,000 light years of distance between the two particles.
Here you're apparently kidding.
Anyways, there's no mentioning of a "line" in this mildly hysterical description of yours; and the actual (chronometric) method is of course rather as laid out above.
Now I drop a black hole halfway along the length of the line.
This seems as if you had the idea that such a black hole had not been "in place" already during the trial(s) of A and B described above. But of course: conditions which are not explicitly forbidden by a setup prescription (including the comprehensive methodology how to determine them) had apparently already been admitted from the outset.
I can no longer "see" particle B from particle A's locale, and vice versa
But sure you can, unless the presumed additional black hole is too large such that A and (by symmetry) B were both inside its horizon.
Has the distance between the two particles changed by the addition of the black hole along the line between the two?
Surely the trial(s) described above can succeed even while the region containing A and B is (significantly and varyingly) curved; e.g. by (not too large) black holes being "dropped", and "added". Accordingly, a value of mutual separation would be attributed to A and B (in either case, with or without black holes being "dropped"); and A and B are accordingly called chronometrically rigid with respect to each other.
But, strictly, a value of "distance" is attributed only to a pair (of "ends") which was and remained chronometrically rigid with respect to each other if, moreover, the region containing this pair had been flat throughout their trials; such that these two ends could (also) be called having been and remained at rest to each other, as two members of the same inertial system.
This is of course not satisfied in case black holes were "dropped" (or already "present") during the trial(s) of A and B. According to this setup prescription, A and B would be attributed a value of their mutual separation (if their trial(s) succeded, as described above), but not a value of (their mutual) distance.