The way I do it is not to use an array but a List instead:
List<int> newOrder = new List<int>();
while (users.Count > 0)
{
int removeIndex = rand.Next(users.Count)
newOrder.Add(users[removeIndex]);
users.RemoveAt(removeIndex);
}
What this does is select an item at random, and then remove it so it can't be repeated.