I found a proof (Here, at the beginning) (it's about the discriminant but still applies for the trace) of the well-known fact that $\text{Tr}_{K|\mathbb{Q}}(\alpha) \in \mathbb{Q}$ which seems to use that if $\beta \in K$ is fixed by all embeddings $K\hookrightarrow \mathbb{C}$, then $\beta \in \mathbb{Q}$.
Now this should be equivalent to being the extension a Galois extension, but for example $\mathbb{Q}(\sqrt[3]{2})|\mathbb{Q}$ is not Galois, so the proof given cannot work in this case.
The proof I thought for a number field would be to use the fact that given $\sum_{i=0}^na_ix^i \in \mathbb{Q}[x]$, minimal polynomial for $\alpha$, then $$\text{Tr}_{K|\mathbb{Q}}(\alpha)=-\frac{a_{n-1}}{a_n}$$
and this should be true for any separable extension $E|F$.
So am I right that the linked proof is not working (without adding Galois extension in the hypothesis at least)?
Are there other easy proofs of the fact that the trace in a separable algebraic extension $E|F$ is an element of the base-field?
The proof you read is fine (although I can't find it in the pdf that's linked in the question).
If $K/\mathbb{Q}$ is any field and $C$ is any algebraically closed field whose cardinality is bigger than that of $K$, then an element $\alpha$ of $K$ will be in $\mathbb{Q}$ if and only if its image under any embedding into $C$ is the same. This is true whether or not $K$ is Galois or even algebraic.
One direction is obvious; for the other, let $f$ be the minimal polynomial of $\alpha$ (both sides of the equivalence are false if $\alpha$ is transcendental); the coefficients of $f$ are rational numbers so it is unambiguously a polynomial with coefficients in $C$, where it splits. There is an embedding of $K$ into $C$ which sends $\alpha$ to any root of this polynomial. It follows that this polynomial is linear (its roots are distinct as we are in characteristic 0).
Your proof is fine too except that what you are writing down may be a fractional multiple of the trace (if your element belongs to a subfield of the field under consideration). But of course this does not change the result that the trace is in $\mathbb{Q}$.