Something that might help, is doing the computations in reverse order. Suppose $n$ is in fact known, and we want to calculate the $99\%$ two-sided confidence interval for the mean.
First, let $X$ be the number of heads in $n$ tosses. Then $X$ is binomially distributed, with $p = 0.5$ and $n = n$. For large values of $n$, we know we can approximate the binomial distribution with parameters $p$ and $n$ with a normal distribution with mean $np$ and variance $np(1-p)$. In this case this means the mean of $X$ is thus $0.5 n$, and the variance is $0.25 n$, so we can approximately say $X \sim \mathcal{N}(0.5 n, 0.25 n)$.
What we are interested in is the ratio of heads. If $Y$ is the fraction of heads, then $Y = X/n$, so $Y$ has mean $0.5$ and variance $\frac{1}{4n}$. Now $Z = \frac{Y - \mu}{\sigma} = \frac{Y - 0.5}{\sqrt{\frac{1}{4n}}}$ is standard normally distributed, with mean $0$ and variance $1$.
We want to make sure that the probability of getting a value of $Y$ between $0.495$ and $0.505$ is at least $0.99$. But we can calculate that probability:
$\begin{align} P(0.495 < Y < 0.505) &= P\left(\frac{0.495 - 0.5}{\frac{1}{\sqrt{4n}}} < \frac{Y - 0.5}{\sqrt{\frac{1}{4n}}} < \frac{0.505 - 0.5}{\frac{1}{\sqrt{4n}}}\right) \\ &= P\left(-0.01 \sqrt{n} < Z < 0.01 \sqrt{n}\right) \\ &\geq 0.99.\end{align}$
Since $Z$ is symmetric around $0$, the left and right excluded tails are the same. So
$\begin{align} P\left(-0.01 \sqrt{n} < Z < 0.01 \sqrt{n}\right) &= 1 - P(Z < -0.01\sqrt{n}) - P(Z > 0.01\sqrt{n}) \\ &= 1 - 2 P(Z < -0.01\sqrt{n}) \\ &\geq 0.99. \end{align}$
Doing a little algebra, we get
$P(Z < -0.01\sqrt{n}) \leq 0.005$
Looking up the $0.005$ in a standard normal table, we know that
$P(Z < a) \leq 0.005 \quad \Leftrightarrow \quad a \leq -2.575$
So this translates to a condition for $n$:
$-0.01\sqrt{n} \leq -2.575 \quad \Leftrightarrow \quad \sqrt{n} \geq 257.5 \quad \Leftrightarrow \quad n \geq 66306.25.$