You can revert this shift by shifting the "legend image" (i.e. the small plot extract that is drawn in the legend) back by the same distance. To do this, set the option legend image post style={xshift=-1cm} as an option to \addplot.
It should be pointed out that using xshift is not really the "proper" way to shift a plot, because it works on the wrong level (you just shift the path, not the "logical" plot). You should instead be adjusting the function: In this case, you should use (x-1)^2 - (x-1) +4 instead of x^2 - x +4.
Another option is to use x filter/.code=\pgfmathparse{\pgfmathresult+1} to manipulate the x-coordinate. This can come in handy if you want to shift the plot without changing the plot expression.
The code below shows all three approaches, also demonstrating the problem with the xshift approach:

\documentclass{article}
\usepackage{pgfplots}
\pgfplotsset{compat=newest}
\begin{document}
\begin{tikzpicture}
\begin{axis}[
xlabel=$x$,
ylabel={$f(x) = x^2 - x +4$}
]
% use TeX as calculator:
\addplot {x^2 - x +4}; \addlegendentry{First plot}
\addplot +[xshift=1cm,legend image post style={xshift=-1cm}]{x^2 - x +4}; \addlegendentry{Second plot}
\addplot {(x+1)^2 - (x+1) +4}; \addlegendentry[]{Third plot}
\addplot +[x filter/.code=\pgfmathparse{\pgfmathresult-2}] {(x+1)^2 - (x+1) +4}; \addlegendentry{Fourth plot}
\end{axis}
\end{tikzpicture}
\end{document}