The first bit, getting the list of speaking characters, is relatively straightforward - you can do it with the *nix command
grep -E "^[A-Z ]+$" script.txt | sort | uniq
which gives a sorted list of all the unique lines containing only capitals and spaces... though that does give you a character of "ACT I" ;-)
Counting the lines, with the underestimate you describe, is doable with a simple state machine. Consider states of "Blank" (blank lines), "Speech" (non-blank lines following a name) and "Action" (non-blank lines not following a name). Transitions are Blank->Speech on a line containing only capitals/spaces, Blank->Action on any other non-empty line, Blank->Blank/Speech->Blank/Action->Blank on an empty line and Action->Action/Speech->Speech on a non-empty line. (Probably clearer as a diagram!) The number of lines you process in the Speech state is the count for the speaker identified in the Blank->Speech transition. It'd end up being about a dozen lines of Perl to do it relatively cleanly.
To fix the underestimate problem, you'll probably want to insert extra "name" lines after an action in the middle of a speech, so it's labelled as a second consecutive speech by the same character - then the automatic counts should work fairly well.
The idea with the matrix is good, and there's a fair amount of computer science literature on similar things: clash graphs and register allocation/colouring. See lectures 5 & 6 here
. Admittedly, I never thought I'd be suggesting applying it to Shakespeare, but the problem of how to optimally allocate roles ("variables") to a small, fixed number of actors ("registers") is completely analogous. One can even see a costume change as the "spill" penalty for an actor having to change roles.
The main thing you're missing is non-speaking characters in a scene - a king addressing his army is very nearly indistinguishable from a monologue. (Adam,Ben) and (Ben,Adam) probably should be the same, but that's true even if only Adam does the talking - he still needs someone to talk at. If you can sort that out (probably by hand-tagging who's in each scene and introducing artificial scene breaks when someone leaves) then the matrix/graph stuff will take care of the rest...