fedja: This is a very nice answer, thank you! (Have you seen/used such a norm ever before?) Before accepting your answer, I'd like to wait a bit, so that other participants feel more encouraged to present other answers.
In fact, let me give here a modification of your answer. I noticed that for $N=3$ your norm of $v=(v_1,\dots,v_N)$ is $\sum_i|v_i-\frac12\,\sum_1^N v_j|$. So, I thought such a modified norm will work as well, for all $N\ge3$, perhaps with some other factor in place of $\frac12$. This seems to work only for $N=3$, though.
However, if I am not mistaken, if $\|v\|:=\max_i|v_i-\frac14\,\sum_1^N v_j|$ for $v=(v_1,\dots,v_N)$, then $\|e_1\|=3/4$, $\|e_1+e_2\|=1/2$, and $\|e_1-e_2\|=1$, so that your main inequality $(*)$ holds for all $N\ge5$.
Only the dimensions $N=3,4$ now remain to be considered.