The problem's in line 6 of your second method. You shouldn't try and remove items from a list of things that you're iterating over. It's better to create a smaller list of things to remove and remove that list from the original one after you're done iterating over it. You might also want to consider using the foreach loop, too.
Other options would be to use a more thread-friendly collection, like those provided in the java.util.concurrent package which are guaranteed to never throw the ConcurrentModificationException. Off the top of my head, the ConcurrentLinkedQueue looks like a good fit. The CopyOnWriteArrayList might work as well depending on needs.
So what would be the main difference in using "CopyOnWriteArrayList" instead of the solution above?
A cat can be deleted from CatsList via method "doThat", would the deleted cat also be in a "CopyOnWriteArrayList" ?
With your code, if you delete a cat from the list while the ArrayList is copying from it then you can get an inconsistent state in the List (cats in the wrong order, perhaps, a null where there should not be an empty spot, a duplicate cat in two consecutive locations. To protect against that sort of thing you would need to synchronize the removal and the copy. CopyOnWriteArrayList prevents such a problem by swapping views internally in a thread-safe manner - preventing you from having to worry about it (and preventing blocking that might happen with synchronized lock contention).