How to most effectively utilize historical data to train churn model
That's correct. You will have the same user multiple times. This can introduce a small bias. I would make a few points why this is better than working with your first approach where you have less data:

First, if the same user shows up in multiple slices that means he doesn't churn or churns later than others. So you bias the model towards figuring out what high retention users look like. As you say:


  So our model could potentially learn that if a particular set of features occurs many times in our data set, then the user with these features is less likely to churn


and this is actually a good thing if you have a good mix of user retention periods. 

Second, you can include the time $t$ as a feature (or their signup date etc.). This will teach your model that users that haven't churned in the past are less likely to churn in the future and reduce the importance the model puts on these other patterns you mention.

More generally, you should not only have a set of static features that don't change for the same user from $t$ to $t+1$. You should also have set of features that is dependent on $t$, e.g. "the number of logins in the last 7 days". That way the model will see differences between the same user at time $t$ and $t+1$.