By a good coloring of a graph $G$ I mean a $2$-coloring of the edges with colors red and blue such that every vertex of degree at least $2$ is incident with a red edge and a blue edge.
Lemma. Let $G$ be a connected graph which is not an odd cycle. If $G$ has at most one vertex of degree different from $2$, then $G$ has a good coloring.
Proof. If all vertices of $G$ have degree $2$, then $G$ is an even cycle. If $G$ has just one vertex $v$ of degree different from $2$, then either $G=K_1$, or else $G$ consists of two or more cycles glued together at one vertex. (Note that $G$ is Eulerian, and consider the cycles traversed by an Euler circuit between successive visits to $v$.) In all these cases the existence of a good coloring is easily verified.
Theorem. Every connected graph which is not an odd cycle has a good coloring.
Proof. We use induction on the size of the graph, i.e., the number of edges. Let $G$ be a connected graph which is not an odd cycle, and assume that the theorem holds for all smaller graphs.
By the lemma, we may assume that $G$ has two distinct vertices, $u$ and $v$, whose degrees are different from $2$. Let $P$ be a path from $u$ to $v$. Color the edges of $P$ alternately red and blue.
Now consider the connected components of $G-E(P)$. Give each component which is not an odd cycle a good coloring, which exists by the inductive hypothesis. However, if any component $C$ of $G-E(P)$ is an odd cycle, then choose a vertex $w\in V(C)\cap V(P)$, and color the edges of $C$ alternately red and blue, except that the two edges incident with $w$ shall have the same color, and if $w$ happens to be an end vertex of $P$, that color shall be different from the color of the edge of $P$ which is incident with $w$.
It is easy to see that this is a good coloring of $G$.
Best Answer
For a complete graph with an even number of vertices, this amounts to finding a 1-factorisation, such as the following:
A general construction is formed by rotating a "starter", such as the following:
Each rotation describes where to place the edges of a single colour. Picture source:
See also the above reference for further details on how to construct 1-factorisations of $K_{2n}$ and near 1-factorisations of $K_{2n-1}$. Hence
For $K_{2n-1}$, we simply start with a 1-factorisation of $K_{2n}$ and delete a vertex, which results in $2n-1$ distinct edge colours. This is the best possible, since each edge colour can occur at most $n-1$ times (without having adjacent monochromatic edges), so we need at least $$\frac{{2n-1} \choose 2}{n-1}=2n-1$$ colours.