Following answer is probably as close to a solution as one can get within reasonable effort. Much of what I'm about to write is based on following two questions and answers therein:
Diagonalizing a [...] Symmetric Toeplitz matrix
[...] determinant of a tridiagonal matrix with constant diagonals
Part 1 - Inverse of $A$
$A$ possesses an inverse, given by
\begin{equation}
(A^{-1})_{nm} = \frac{1}{1-e^{2i \phi}}
\begin{cases}
1 & n = m = 1, N \\
1+e^{i\phi} & n = m \\
- e^{i\phi} & |n-m| = 1 \\
0 & \text{otherwise}
\end{cases},
\end{equation}
i.e., the inverse of $A$ is a tridigonal matrix with near constant diagonals, except for $(A^{-1})_{1,1}$ and $(A^{-1})_{N,N}$.
Part 2 - Characteristic Polynomial of $A^{-1}$
For the calculation of the characteristic Polynomial
$$\chi(\lambda) = \det\big(A^{-1} - \lambda\big)$$
it's useful to consider the substitution
$$\lambda = \frac{1}{1-e^{2 i \phi}} \mu + \frac{1+e^{2i\phi}}{1-e^{2i\phi}}.$$
With that, we have $\det(A^{-1} - \lambda) = 0 \Leftrightarrow \det(\tilde{A}^{-1} - \mu) = 0$ with
\begin{equation}
\tilde{A}^{-1} =
\begin{cases}
-e^{2i\phi} & n = m = 1,N \\
-e^{ i\phi} & |n-m| = 1 \\
0 & \text{otherwise}
\end{cases}
\end{equation}
Now, by defining the auxilliary $N\times N$ matrix $B_N$ which contains $-e^{i\phi}$ on the first of diagonals and $0$ on all other elements (i.e. $(B_N)_{n,m} = (\tilde{A}^{-1})_{n,m}$ expect for $(B_N)_{1,1} = (B_N)_{N,N} = 0$), one derives
\begin{equation}
\det(\tilde{A}^{-1} - \mu) =
(e^{2i\phi} - \mu)^2 \det(B_{N-2}) + 2 e^{2i\phi} (e^{2i\phi} - \mu) \det(B_{N-3}) + e^{4i\phi} \det(B_{N-4}).
\end{equation}
For $\det(B_N)$ one can derive a recursion relation, like in the second linked question, which gives $\det(B_N)$ in terms of Chebyshev polynomials. For $\mu^2 \ne 4 e^{2i\phi}$ and after one further substitution $\tilde{\mu} = \mu e^{-i\phi}$ one finds the characteristic Polynomial
\begin{align}
&\det(\tilde{A}^{-1} - \mu) = 0 \Leftrightarrow \\
&\color{blue}{(e^{i\phi} - \tilde{\mu})^2 U_{N-2}(\tilde{\mu}/2) - 2(e^{i\phi} - \tilde{\mu}) U_{N-3}(\tilde{\mu}/2) + U_{N-4}(\tilde{\mu}/2) = 0},
\end{align}
where $U_N$ is the Chebyshev Polynomial of the second kind.
Part 3 - short discussion
With the knowledge of the solutions of the characteristic equation for $\tilde{\mu}$ on directly finds the the eigenvalues $\lambda$ of $A^{-1}$ and, with that, for $A$. $U_N(x)$ is a polynomial of degree $N$ with $N$ distinct roots $x_k = \cos(\pi k/(N+1))$ with $k=1,\dots,N$. One may hope, that these are sufficiently close to the actual roots and do pertubation theory on those roots (e.g. by using Newton's method to calculate corrections to $x_k$). However, we are calculating the eigenvalues of $A^{-1}$ and some of the (approximative) eigenvalues $x_k$ lie close to $0$ (namely for $k$ close to $N/2$). Thus, small corrections to those, mean enormous corrections to the resulting approximative eigenvalue of $A$. Therefore finding approximative eigenvalues with the above stated "algorithm" is not well suited.
Finally, there is one more option, to get to a "simpler" eigenvalue equation for $A^{-1}$. By substituting once more $\tilde{\mu} = \nu + \nu^{-1}$ the Chebyshev Polynomials reduce to $U_N(\tilde{\mu}/2) = \nu^{N-1}-\nu^{-N+1}$. After rearranging some powers one ends up with
\begin{align}
&\det(\tilde{A}^{-1} - \mu) = 0 \Leftrightarrow \\
&\nu^{2N}(e^{i\phi} + \nu)^2 - (1 + e^{i\phi}\nu)^2 = 0.
\end{align}
Notice, this is now a polynomial of degree $2N+2$, however $\nu = \pm 1$ is a solution, which we already excluded, since we assumed $\mu^2 \ne 4e^{2i\phi}$ and all other roots come in pairs: if $\nu_k$ is a solution, so is $\nu_k^{-1}$. However, they provide the same $\tilde{\mu}$ after resubstitution. All in all, while this polynomial equation is much more compact, it didn't helped me find a closed form solution or an good approximation of the original problem (this is, the eigenvalues of $A$).
