The eigenvalues of a square matrix $A$ coincide with the roots of its characteristic polynomial $p[A]$. Conversely, if I have a polynomial $$ a_0 + a_1 x + \cdots + a_{n-1}x^{n-1} + x^n ~, $$ I can define a companion matrix $$ A[p]=\begin{bmatrix} 0 & 0 & \dots & 0 & -a_0 \\ 1 & 0 & \dots & 0 & -a_1 \\ 0 & 1 & \dots & 0 & -a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -a_{n-1} \end{bmatrix}.$$ The characteristic polynomial of the matrix $A[p]$ is the original polynomial $p$. The companion matrix defined in this way is not Hermitian.
Edit: Consider only hyperbolic polynomials, i.e., polynomials which have only real roots.
However, the companion matrix is not the only matrix whose characteristic polynomial is the polynomial $p$. For an example, just consider the diagonal matrix of the eigenvalues ${\rm diag}{(\lambda_1,\lambda_2,\ldots,\lambda_n)}$. This matrix is indeed Hermitian, but one needs to calculate eigenvalues, which can be a difficult task for large matrix sizes.
Therefore my question is: Is it possible to define a "companion" matrix (a matrix whose characteristic polynomial is the given polynomial $p$) which is Hermitian, and which is easier to calculate than the diagonal matrix of the eigenvalues ${\rm diag}{(\lambda_1,\lambda_2,\ldots,\lambda_n)}$? With easy to calculate I mean a matrix which can be written in terms of the parameters $a_i$ and without calculating the eigenvalues.
The answer is no in general since Hermitian matrices have real eigenvalues. So for example, there is no Hermitian matrix whose characteristic polynomial is $X^2+1$.
Even if you restrict to polynomials with real roots, I doubt you can find a simple formula : I think that if there is a rational formula that works for every polynomial with real roots, it should also apply to all polynomials. Let me explain what I mean precisely. We'll use the following lemma which states that when rational equations hold for polynomial with real roots, they should hold everywhere. Denote $\mathbb{C}_{n,u}[X]$ the set of monic complex polynomials of degree $n$.
Lemma : Let $f$ be a rational function
$$\begin{eqnarray*}f :& \mathbb{C}_{n,u} & \longrightarrow \mathbb{C}^N\\ & P &\longmapsto f(P)\end{eqnarray*}$$
such that $f$ is zero on polynomial with real roots. Then $f$ is zero.
Proof :
The map
$$\begin{eqnarray*}p_n :& \mathbb{C}^n & \longrightarrow \mathbb{C}_{n,u}[X]\\ & (\lambda_1, \ldots, \lambda_n) &\longmapsto p_n(\lambda_1, \ldots, \lambda_n) = \prod_{i = 1}^n (X-\lambda_i)\end{eqnarray*}$$
is also a rational map (meaning the coefficients of a polynomial are rational functions of its roots, and we can actually compute them, those are called elementary symmetric polynomials). By hypothesis, the function $f \circ p_n$ is zero on $\mathbb{R}^n$. But since $f \circ p_n$ is rational, it is actually zero everywhere, and because $p_n$ is surjective (every polynomial is split in $\mathbb{C}$), then $f$ is zero.
Now assume there is a rational function
$$\begin{eqnarray*}A_n :& \mathbb{C}_{n,u}[X] & \longrightarrow \mathcal{M}_n(\mathbb{C})\\ & P &\longmapsto A_n(P)\end{eqnarray*}$$
(by that I mean that the coefficients of the matrix $A_n(P)$ are rational functions of the coefficients of $P$) such that the characteristic polynomial of $A_n(P)$ is $P$ whenever $P$ has real roots. This means the rational function $P \longmapsto \det(XI_n - A_n(P)) - P$ is zero on polynomial with real roots, so it's zero everywhere, which means the characteristic polynomial of $A_n(P)$ is always $P$ without assumption on the roots of $P$.
Assume moreover that $A_n(P)$ is hermitian whenever $P$ has real roots. Then I claim $A_n(P)$ is hermitian for any real polynomial $P$ from the same kind of argument. Indeed denote $A_n^* : P \longmapsto \left[A_n(P^*)\right]^*$, where $P^*$ denotes the complex conjugate of the polynomial $P$, and $\left[A_n(P^*)\right]^*$ is the conjugate transpose of the matrix $A_n(P^*)$. This is a rational function (beware that $P \mapsto [A_n(P)]^*$ is not rational however !). Our assumption is that the rational function $A_n - A_n^*$ is zero on all polynomial with real roots, so it's zero everywhere. When $P$ is real, this means $A_n(P)$ is hermitian (because $A_n(P) = A_n^*(P) = [A_n(P)]^*$, the last equality being only true when $P$ is real). This yields a contradiction if $P$ is a real polynomial with complex roots.