The following idea comes from a Chinese blog.
Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.
We have the following observations:
All vertices not in $M$ must belong to $\mathrm{Never}$.
Proof. Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$.
Proof. Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$.
These observations lead us to the following algorithm:
A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
i = i + 1
A[i] = empty set
for each vertex v in N[i - 1]:
temp = N(v) \ A
A[i] = union(A[i], temp)
A = union(A, temp)
if A[i] is empty:
break
for each vertex v in A[i]:
add M(v) into N[i]
add M(v) into N
After the execution of this algorithm, all vertices in A belong to $\mathrm{Always}$ and all vertices in N belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in A forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.
