There is no standard way of presenting a vector space other than by presenting a basis, and so there is no standard way of presenting a linear map between two vector spaces other than a matrix (or something that is equivalent to a matrix, e.g., defining the map on a large enough collection of vectors). So any situation where you are trying to compute eigenvalues and you do NOT have a matrix (or something easy to convert to a matrix) will be slightly contrived.
The easiest example I can come up with is the following: Let $V$ be the collection of polynomials of degree at most $5$, and let $T:V\to V$ be the map sending a polynomial to its derivative. Since the derivative lowers the degree of a polynomial by one (until it is constant, and then equal to zero, at which point the process stabilizes), we have that $T^6$ must be the zero map. This tells us that the minimal polynomial divides $x^6$, and since the characteristic polynomial and the minimal polynomial must share the same roots, the characteristic polynomial must be $x^6$ too. Therefore, $0$ is the only eigenvalue. What are the corresponding eigenvectors? Since differentiation lowers degree by exactly one, only constant polynomials have zero derivative, and the constant polynomials are spanned by the vector $1$.
So here, we had an example of a linear transformation which we could analyze without putting it directly into matrix form because we could find a polynomial it satisfied just by using general properties we knew. So it can be done in some situations. However, doing it in general requires having some way of deducing properties of the transformation, and that usually isn't strictly a matter of linear algebra.