Deleting would be the better option if you use an ArrayList instead of an array. Because in case of array, you would have to either re-size it (that means, you have to create a new array everytime - Deadly idea. Avoid it), or set the index selected to null.
But the problem with this approach (Setting null) is that, you may have to do random selection many times to get one valid random index especially when you are left with only 1 valid index. So, it's better to use a List, and delete the selected element from it.
List<String> list = new ArrayList<String>();
// Populate your list.
Collections.shuffle(list); // Shuffle the list.
String random = list.remove(0); // Will remove the first element
Note that, if you want your original ArrayList, later one, then probably you can make a copy of it.