The TERM environment variable should be set by the application that is acting as your terminal. This is the whole point of the thing: letting programs running inside them know what terminal is being used and hence what sort of features it supports.
Zsh is not a terminal. It is a shell. It might care what your TERM is set to if it wants to do special things, but it should not be responsible for setting it. Instead it is responsible for setting variables such as ZSH_VERSION which can be used by scripts or other child processes to understand what behavior to expect from their parent shell.
Instead, you need to check the configuration for whatever terminal application you are using and ask it to report itself properly. For example you can do this for xterm by adding this line to the
~/.Xdefaults file it uses for configuration values:
It appears gnome-terminal does the idiotic thing of reading what your xterm configuration would be instead of having it's own. This might get you by in some cases but is should more properly be set to vte-256color. This appears to be a long standing gripe against it (and some other VTE based terminal emulators). A common way to hack around this is exploit another value it does set:
if [ "$COLORTERM" = "gnome-terminal" ]; then
But this brings you back around to your problem with tmux, so you would have to account for that by not resetting TERM if it is already something like "screen-256color" or "screen":
if [ "$COLORTERM" = "gnome-terminal" -a "$TERM" =~ xterm.* ]; then
For other terminals you will need to lookup their proper configuration routines.