After many days of thought, I have come up with a proof for complex polygons. I will not accept my answer until I either edit it with a proof for non-planar polygons too or someone else is able to answer that part of my question.
The first thing to do is to disqualify any polygon with overlapping colinear (not necessarily consecutive) edges. If a walk through the edges would demonstrate that these edges are walked through in the same direction twice that means that a total turn of at least $2\pi$ has already been made between the two edges, yet the traversal has not yet concluded. Otherwise, if the edges are walked over in opposite directions, that would require a total turn of at least $\pi$ to turn around at each end of these edges. If that is all the turns that there are, then this sequence of points has only two significant points and does not form a polygon. The number of significant (non-colinear) vertices will have to be checked separately.
Now that we've gotten that out of the way, we may proceed with the assumption that no edges overlap. Note, this also means that no interior angle is equal to 0, $\pi$ or $2\pi$ radians, which means that no exterior angle is $\pm\pi$ or 0 radians, which in turn means that no turn (the absolute value of the exterior angle) is 0 or $\pi$ radians.
For any complex polygon $P$, we are able to find a sequence of consecutive vertices of $P$ which when appended to an intersection point of $P$ forms a simple polygon in the following way.
We choose any arbitrary point on the polygon's bounding path. Then from that point we trace the bounding path, marking any intersection points we encounter. Once we arrive at an intersection point which we've previously encountered, we stop. Let this intersection point be called $I$.
The closed path which we traced from the first encounter with $I$ to our second encounter with $I$ is a simple polygon (see figure).

Figure: Extracting a simple polygon from a complex one. This complex polygon is a pentagram with vertices $v_0$ through $v_4$. $S$ is the arbitrarily chosen starting point. The orange arrowhead marks the bounding edges of a simple polygon $E = (v_0, v_4, v_3, I)$ embedded in the complex pentagram. $I$ is the first (and necessarily the only) intersection point of the pentagram which we encountered twice.
The embedded polygon $E$ found with this procedure must be simple since we stop our trace at the first intersection point we encounter twice. Thus all of $P$'s intersection points are touched only once by $E$, except for point $I$ which is the start and end point, so is not an intersection point of $E$ either.
Let $\alpha \in (0, 2\pi) - \{\pi\}$ be the interior angle of $E$ at vertex $I$, and let $\beta = \pi - \alpha \in (-\pi, \pi) - \{0\}$ be the exterior angle of the same.
Suppose now we were to 'walk' a cycle through the edges of $P$ starting at the midpoint of the line segment formed by $I$ and one of the two vertices adjacent to $I$ which is common to both $P$ and $E$ (either $v_0$ or $v_3$ in the figure). Suppose we start walking in the direction away from $I$ and are only allowed to walk forward and turn.
The first time we reach $I$, we will have already turned all the turns of $E$ but one --- $T_E(I)$ (the turn of polygon $E$ at vertex $I$), which is equal to $|\beta|$. We immediately pass $I$ and enter a section of the path which is no longer part of $E$. Let us analyze the current position.
Since $I$ is an intersection point of $P$, we will in future be forced to encounter it again before arriving finally at the start. However, since we've just passed $I$, it is positioned a small distance directly behind us. This means that in order to reach it in future, our path must force us to make some turns which sum to at least $\pi$ radians.
This now allows us to formulate our first inequality. ($\sum T_P$ means the total turn of the polygon $P$, that is the sum of the turn at each of its vertices)
\begin{equation}
\sum T_P \geq \sum T_E - |\beta| + \pi
\end{equation}
Since we know that $\sum T_E \geq 2\pi$ due to the simplicity of $E$, and that $\beta \neq \pm\pi$ from the first paragraph of the proof, we can from the previous inequality come to the following conclusion.
\begin{equation}
\sum T_P \geq 3\pi - |\beta| > 2\pi
\end{equation}