Here's a somewhat related article...
http://dresdencodak.tumblr.com/page/5
vs.
Changing hairdos and trying small displacements won't register as different characters. Sure these drawings are exaggerated but it's the same for realistic characters too. Reusing the same head with slight modifications has never worked, using 4-5 separate heads has always been better.
So, regarding your question about building characters for Infamous, I have no straight answer because too much is unknown, but I can give you some more examples on how we've dealt with character variations previously.
The restrictions are the most important, especially the budget: how many man-months can we spend on it. Also, what are the skill levels of the people involved, what are the render time limitations (we have such, too). What are the rigging and animation related limitations (use of cloth simulation, hair and so on).
For the original Assassin's Creed 2 intro we needed to build a lot of carnival dancers.
We had a single male and female body type to speed up the simulation and most of the variety was in the robe types and headwear/masks, then we expaned it using the textures (the lighting and shaders emphasized the patterns on the fabrics).
We had a randomizer tool, but the way we ended up using it was to render a sequence of all the resulting combinations, then the art director went through it and marked the ones that looked good enough and were okay to use. The completely random combinations looked pretty bad sometimes.
For a recent project that involved, well, zombies, we skipped the randomizing completely. We had the same skeleton, three body types, three kinds of upper/lower/footwear, a few types of hair and a cap. Each torso mesh had 3 head variations using a blendshape and a set of displacement/normal maps (we were unable to go with separate head meshes). The faces didn't turn out to be as good as we've hoped, by the way, partially because we couldn't change eye and mouth positions as the eyeball/teeth geometry couldn't be moved. Still we had to be careful with the various hair/cap and head combinations.
We've then created a large character sheet in Photoshop and manually designed about 20 fixed variations, named each of them and went on with no randomization/proceduralism at all. So it was like character A has body type 1, head type 2, t-shirt with texture 1, jeans with texture 3 and so on. We've found that it worked far better as we could fit the styles of the various cloth pieces better, you wouldn't wear the pants of a suit with a T-shirt for example. Combined with the females we had about 30 unique characters which doesn't sound much but it was enough and none of them looked ridiculous.
We thought about adding stuff like zombified policemen/firemen, but that's a very complex issue. These kinds of characters stand out from a crowd in several ways - you immediately notice a cop among civilians because of the uniform, so you have very limited reuse of this asset. It also separates the crowd into civilians and the other kind, so to get him to blend better, you'll have to add other characters with such stand-out features (firemen, construction worker, supermarket sales crew, waiter etc etc). So you have to build a lot more of these assets that still have very, very limited use - so this is something you can only do if you have a very large budget.
Then there's the question of height and age which is very similar. One kid will stand out, and unfortunately multiple kids will only work if they're not all the same age and height. But proportions change very distinctively with age: small kids are 4 head-lenght tall, an adult is 7-8 head-length tall, so you'd also have to cover several variations inbetween. Each age group also needs a new skeleton and new sets of animations, and it's important to accept that you can't create these procedurally, so once again it requires an extension of the budget. Oh, and kid's clothes are different, you don't want to see old people wearing young people's clothing, and so on and so on.
So this is why we ended up with about 30 people for the crowd, it was enough for our purposes and they didn't look that much different to the 4 'hero' characters in the movie (but different enough to still register as less detailed, unfortunately).
If we had to create a much larger cast with the same budget and tech restrictions, we would have had to go with some procedural tool but it would've looked a lot worse. It'd also require a more serious tool development, so that we could restrict the combinations using rules; and probably come up with a method to fit clothing and acessories to the various body types more automatically so that the artists can concentrate on building the base assets (but this is definitely more complicated for characters with fully simulated clothing, compared to today's games where everything is just skinned to a skeleton).