Some ideas are:
- You branch off into another timeline and your actions make no difference to the previous timeline
- You’ve already taken said actions but just didn’t know about it so nothing changes
- Actions taken can have an effect (so you could suddenly erase yourself if you killed your parents)
- Only “nexus” or fixed events really matter, the timeline will sort itself out for minor changes
- something else entirely
You’re assuming that time travel is equivalent to “rewinding” the intervening time span as if it had never occurred—in which case, yes, nondeterministic events are likely to happen differently.
But that’s not the case if time travel is a closed time-like loop (which is implicit in the “immutable-past” of OP’s second scenario). In that case everything happens only once, so it makes no difference whether or not the universe is strictly deterministic.