First we establish the upper bound by exhibiting a 3-(total-)coloring for $C_n$ when $3\mid n$ and a 4-coloring for all $n$.
When $n\mid 3$ color the vertices red, green, blue cyclically.
Color the edge between two vertices with the only color that is not used on its endpoints. This is a proper total coloring with 3 colors (verify!).
When $n$ is even we alternately color the vertices with red and green, and we alternately color the edges with blue and yellow.
This is a proper total coloring with 4 colors (verify!).
When $n$ is odd we go clockwise around the cycle and start coloring vertices alternately with red and green. The last vertex would cause two adjacent red vertices, so we color it blue instead. Now we walk around the cycle again and when we go from a red to a green vertex we color the edge blue, when we go from a green to a red vertex we color the edge blue, when we go from a green to a blue vertex (only once) we color the edge red and when we go from a blue to a red vertex (only once) we color the edge green.
This is a proper total coloring with 4 colors (verify!).
Since $\chi''(G)\geq\Delta(G)+1=3$ we are already done with the case $3\mid n$.
For the last part we need to show that no proper 3-total-coloring is possible,
unless $n$ is a multiple of 3.
Let $v_1,\ldots,v_n$ be the vertices of $C_n$ and assume we have a proper 3-coloring. $v_1$, $v_2$ and edge $v_1v_2$ must have all different colors, say red, green, blue respectively. Now edge $v_2v_3$ cannot be green or blue, so it must be red. Vertex $v_3$ cannot be green or red, so it must be blue. Continuing this process you see that the entire coloring is forced and that we end up with a cyclic coloring of the vertices with period three just as we used above (verify!). Clearly this is only possible when $n$ is a multiple of 3.
The block decomposition of a graph leads to a tree. Assume that all the blocks of $G$ have been colored but two blocks $B_1,B_2$ do not agree about the coloring of their common vertex. Then by rotating/replacing the colors in one of the two blocks we may resolve such issue. Due to the tree-structure of the block decomposition, we may pick a block as "root" and resolve all the color-conflicts, proceeding from the root to the leaves and fixing the colors of the children blocks each time.
Best Answer
A counterexample is given by the five-cycle $a-b-c-d-e-a$. Its chromatic number is three. It is minimal in that if you remove any edge the chromatic number goes down to two. But if you remove $a-b$ and put in $a-d$ then the chromatic number remains three.