First off, I am aware of this answer: Show that $E(X)=\int_{0}^{\infty}P(X\ge x)dx$ for non-negative random variable $X$, but I want to know what is missing in my approach. I would calculate as follows $$E(X)=\int_{-\infty}^{\infty}xP(dx)=\int_{-\infty}^{\infty}\int_{0}^{x}dyP(dx)$$
where I use Fubini with $$0<y<x \text{ and}-\infty<x<\infty$$ giving $$0<y<\infty\text{ and } y<x<\infty$$ hence the above expression becomes $$\int_0^{\infty}\int_y^{\infty}P(dx)dy=\int_0^{\infty}P(X>y)dy$$
Now this is the right solution but nowhere did I (explicitly) use that $X$ is non-negative. Could someone point out what I am missing.
Since you didn't assume $E|X|<\infty$ you need non-negativity to switch the order of integration. The version of Fubini for non-negative r.v. is sometimes called Tonelli's theorem.
Check out wikipedia's entry on Fubini's theorem and its counterexamples.