How many people do we need so that the probability of someone having the same birthday as Person A is 100%? 
Suppose you have some designated Person A. How many people do we need so that the probability that one of those people has the same birthday as person A is 100%?

The first thing that came to my mind was $365$, but that doesn't have to be true. Some of those $365$ people could have the same birthday, so the Person A's birthday doesn't have to be covered. I thought of calculating probability that $n$ people don't share the birthday with Person A. Then $1$ minus that probability, I don't know how to calculate that. It seems to me that the probability I am asking for will never be 100%.

You are correct.
Given person $A$'s birthday, for each other person there is a probability of $364/365$ (ignoring leap years) that they do not share a birthday with $A$.
Therefore if there are $n$ others, then there is a probability of $(364/365)^n$ that none share a birthday with $A$, hence a probability of $1-(364/365)^n<1$ that at least one does share a birthday with $A$. 
