How do I give objects with the same texture, a different viewport color?
First, select one of the desired objects and give it a new material with a new color.


Then pick all the other elements you want to change the material on.  You can add to the current selection with Shift + Click.  Finally select the object with the new material.

Then you can press Ctrl + L and select Materials to carry the material of your last selection over to all the other selected objects.