"to do over" means " to do something again from the beginning, especially because you did it badly the first time"
I have the impression that "to do over again" has the same meaning(so it can be as early as only being the second attempt) but according to my logic it should be at least the 3rd time since it's "to do over" and "again"