Example (ii): St Paul converts Gentiles but also accepts that they must become Jews before they become Christians.
Result: A smaller Jewish Christian Church that would not be able to unify the Roman Empire unless it had a further split. Every alternative generates others and I cannot imagine the timeline beyond that point.
Example (iii): Paul believed that Jesus' return was imminent. How might this idea be used in fiction? A fantasy novel in which Jesus did return? That would be an alternative history and definitely not a time travel story.
Causality violation can transform time travel into alternative history, e.g., in two installments of Poul Anderson's Time Patrol series. However, many alternative histories are independent of time travel, especially those in which magic works or the supernatural exists, e.g., in Anderson's two Operation... volumes.