I don't know how to answer just in the comments, so here's a non-solution reply to your question.

Is there any principle you can articulate by which one could make one's code more robust to this kind of thing?

There are two side-effect-dependent patterns here. The first is simply

something[[idx]] = new

This kind of modifying in place is rarely necessary, so should be used only when nothing else will do. For example, you could repeatedly increment a randomly chosen element like this:

Nest[Function[list, MapAt[# + 1 &, list, RandomInteger[{1, 2}]]], {a, b}, 5]

This allows the evaluation engine to manage the state changes.

The second is co-mingling the "choice" logic with the "update" logic by having the RandomInteger expression explicit in the update expression. Whenever you use a Random* function directly, you make things harder to test. Your concern now is that all of your simulations are corrupted, and that's why we want to be able to test things directly. Yes, you can use SeedRandom, but then you still need to know what actual sequence of random variables was used to verify the results. Usually better to separate out the thing that will be random and then swap later after you've convinced yourself that things are working. So, something like

myPrivateVariable = 1;
myIndexChooser[] := myPrivateVariable = Mod[1 + myPrivateVariable, 2, 1];
Nest[Function[list, MapAt[# + 1 &, list, myIndexChooser[]]], {a, b}, 5]

I'd do more to encapsulate the private variable, and I'd probably do something more sophisticated in terms of the actual chooser implementation, but this shows the gist. You don't always need a full-blown chooser function, just some way to separate the making of the choice from the applying of the choice. So even this can work:

With[
  {idx = RandomInteger[{1, 2}]},
  x[[idx]]++]

None of this is to say that there isn't a real bug here. And I wouldn't say that the above things should be used because there somehow resilient to language implementation bugs. I'm just saying that your style of programming already has some other risks independent of the fact that you hit on an actual bug.

Update

Or, given kglr's explanation, which makes it seem obvious in hindsight, your side-effect based and conflated code style was indeed the cause of your errors.

I suspect this is a subtle interaction between the HoldFirst attribute of Increment and the HoldAll attribute of While.

Possible Fix? Adding a semicolon inside the While block in your second code, i.e.,:

ch = ConstantArray[0, 2];
While[Min[ch] == 0,
 ch[[RandomInteger[{1, 2}]]]++;];
ch

appears to resolve the problem. (A similar modification to your second example also brings the two results into agreement.)

Note added in edit: In the comment thread, @kglr seems to have found that this doesn't work.

A functional alternative (added 11 Nov)

I'm in agreement with @lericr ... I wouldn't implement it the way that the OP did, as it seems like it opens up a possible confusion about operation order. I would personally be inclined to implement it in a more functional style like the following:

update[state_] := With[
  {index = RandomInteger@Range@Length[state]},
  state + UnitVector[Length[state], index]]

NestWhile[update, {0, 0}, ContainsAny[{0}]]

Turns out we have a bonafide Wolfram Language bug here. With help from you all, I've pared it down to this:

SeedRandom[0];
x = {a, b};
x[[RandomInteger[{1, 2}]]]++;
x

Bizarrely, that returns {1 + b, b}. The a gets lost. Instead of incrementing either the first or second element of x it adds one to the second element and replaces the first element with it.

PS: As @kglr has explained, the reason this happens is that RandomInteger is called twice. Once to pick the element and once again to do the incrementing. This version may illustrate that better:

callcount = 0;

getindex[] := (Print["the index is ", callcount+1]; ++callcount)

array = {a, b, c};
array[[getindex[]]]++;
array

The output:

the index is 1
the index is 2
{a, 1 + a, c}

Which confirms that getindex[] is called twice and, since it returns different values each time, the results are all wrong, assigning the first element plus one to the second element.