For sake of completeness, I am writing a full answer based on the suggestion of
Pietro Majer.
The following are equivalent:
1) $A$ is an isometry w.r.to some norm.
2) $A$ is diagonalizable (over $\mathbb{C}$) , with all eigenvalues of modulus 1.
3) All orbits of $A$ are bounded ( $\sup_{k\in\mathbb{Z}}\|A^k x\|<+\infty$ for any $x\in \mathbb{R}^n$).
4) $A$ is an isometry w.r.to some inner product.
$(1)\iff (4)$ leads to an interesting point: The union of all isometries of all norms equals the union of all isometries of all inner products.
Proof:
$(1) \Rightarrow (2):$
Assume $||$ is a norm preserved by $A$. Then the operator norm of $A$ w.r.t to $||$ equals 1. Also $||A^n||_{op}=1$. By the spectral radius formula: $\rho(A)=\lim_{n\rightarrow\infty}||A^n||^{1/n}=1 $. The same argument for $A^{-1}$ implies $\rho(A^{-1})=1$. This implies all the eigenvalues (including the complex ones) are of absolute value one.
Also, it is easy to see that If $A$ is an isometry of the norm $| |_1$ , $P∈GL(\mathbb{R^n})$, $P^{−1}AP$ is an isometry of the norm $||_2$ where $||x||_2=||Px||_1$. Thus, the property that a given matrix admit such a norm is invariant under similarity.
So it is enough to focus upon matrices of Jordan form. (which is available to us since we work over $\mathbb{C}$).
Now assume $A$ is not diagonalizable. By looking at Jordan form of a non-diagonalizable matrix, we can see there is a vector $v∈\mathbb{C}^n$ such that $||A^kv||_{Euclidean}$ diverges. (Look at the example of $\begin{pmatrix} 1 & 1 \\\ 0 & 1 \end{pmatrix}$ given in the question).
Since all the norms are equivalent This implies that $||A^kv||$ diverges. But since $v=x+iy$ with $x$ and $y$ in $\mathbb{R}^n$, and $A^kv=A^kx+iA^ky$, either $||A^kx||$ or $||A^ky||$ diverge. This is impossible if $A$ is an isometry of $||$.
$(2) \Rightarrow (4):
$ This is proved here (The basic idea is to look at each Jordan block separately).
$(4) \Rightarrow (1):$ Obvious.
It remains to prove $(1) \iff (3)$:
$(3) \Rightarrow (1):$ If all orbits of $A$ are bounded, then we can renorm $\mathbb{R}^n$ by $\|x\|_A:=\sup_{k\in \mathbb{Z}} \|A^k x\|$, which is an $A$-invariant equivalent norm.
$(1) \Rightarrow (3):$ This follows immediately by the fact all norms on a finite dimensional vector space are equivalent. The orbits of $A$ are all of constant norm ($\|x\|$) w.r.t to the norm $A$ preserves, hence are bounded. (w.r.t any other norm).
Best Answer
As pointed out by YCor in the comments, the following theorem is true:
Theorem 1 Let $p \in [1,\infty] \setminus \{2\}$. If a matrix $A \in \mathbb{R}^{n \times n}$ is an isometry on $\mathbb{R}^n$ with respect to the $p$-norm, then $A$ is a signed permutation matrix, i.e. a permutation matrix where some of the one's are replaced with $-1$.
For the proof, first note that the case $p = \infty$ follows from $p = 1$ by duality, so we only have to show the theorem for $\in [1,\infty) \setminus 2$.
Now we use the following lemma:
Lemma 2 Let $p \in [1,\infty) \setminus \{2\}$ and let $(\Omega_1,\mu_1)$ and $(\Omega_2,\mu_2)$ be two measure spaces. If $T: L^p(\Omega_1,\mu_1) \to L^p(\Omega_2,\mu_2)$ is an isometric linear mapping, then $T$ is disjointness preserving, i.e. for all $f,g \in L^p(\Omega_1,\mu_1)$ which fulfil $fg = 0$, we also have $(Tf)(Tg) = 0$.
In a more general form, this lemma goes originally back to Lamperti ("On the isometries of certain function spaces", Pacific J. Math. 8 (1958), 459–466.).
A very clear proof of the lemma in the above form can be found in Lemma 4.2.2 of S. Facklers PhD dissertation (DOI: 10.18725/OPARU-3268).
If we apply Lemma 2 to $L^p(\Omega_1,\mu_1) = L^p(\Omega_2,\mu_2) = \mathbb{R}^n$, it follows that every matrix $A \in \mathbb{R}^{n \times n}$ which is isometric with respect to the $p$-norm is automatically disjointness preserving. Hence, every row of $A$ contains exactly one non-zero entry. Since $A$ is invertible, this implies that every column of $A$ also contains exactly one non-zero entry. Thus, $A$ is of the form $A = DP$, where $P$ is a permutation matrix and $D$ is a diagonal matrix. Using again that $A$ is isometic, we can see that $D$ can only have the numbers $1$ and $-1$ on its diagonal.
Remarks:
(a) Lemma 2 is of course quite general compared to the finite dimensional question. However, I don't think that a finite dimensional version of Lemma 2 is easier to prove.
(b) Using Lemma 2 above, one can also obtain a description of isometries on general $L^p$-spaces; see Theorem 3.1 in Lamperti's article quoted above.