The phrase "the set of all linear combinations of vectors from $M$" refers to the set of all vectors of the form
$$a_1x_1 + a_2x_2 + \cdots + a_kx_k$$ where $k$ is a nonnegative integer, $a_1,\ldots,a_k\in\mathbb{R}$ and $x_1,\ldots,x_k\in M$.
For example, the span of $\{x_1,x_2,x_3\}$ is defined to be the set of all vectors expressible in the form
$$a_1x_1 + a_2x_2 + a_3x_3,$$ for $a_1,a_2,a_3\in\mathbb{R}.$
In the particular example of $x_1,x_2,x_3$ that you gave, notice that for any $a,b,c\in\mathbb{R}$, some computation shows that
$$\langle a,b,c\rangle = (a+5b-2c)x_1 + (a+4b-2c)x_2 + (c-b)x_3$$
and so every point $\langle a,b,c\rangle\in\mathbb{R}^3$ is in the linear span of this set. That is, in this example, $\mathrm{span}\{x_1,x_2,x_3\} = \mathbb{R}^3$.
Assume the field is $\mathbb{C}$. Then the vector space $\mathbb{C}^n$ is a representation of the symmetric group $S_n$. It is well-known that this is a direct sum of the trivial representation spanned by $v=(1,\cdots,1)$ and the kernel of the linear map $L(x)=v\cdot x$, that is $\{(x_1,\cdots,x_n)\mid x_1+\cdots+x_n=0\}$. These two representations are both irreducible. Any subspace spanned by permutations of a particular vector $x$ will be the cyclic submodule generated by $x$ (recall $S_n$-representations are $\mathbb{C}[S_n]$-modules). Thus, by semisimplicity, the only possible dimensions will be $0,1,n-1,n$. (I thinks this works over arbitrary fields, or at least characteristic zero.)
Low-tech version. Let $V$ the space spanned by $v=(1,\cdots,1)$ and let $W$ be the aforementioned complementary subspace. Notice $W$ is spanned by $(1,-1,0,\cdots),\cdots,(0,\cdots,1,-1)$.
Let $x=(x_1,\cdots,x_n)$ be arbitrary. The dimension is $0,1,n-1,n$ based on:
If $x=0$ then the span is $0$.
If $x\ne 0$ and $x\in V$ then the span is $V$.
If $x\in W$ then permute it so two distinct components are next to each other. Sum over every permutation of the other $n-2$ components, call it $u$. Let $u'$ be $u$ with the chosen two components swapped. Then $u-u'$ is a scalar multiple of any one of $W$'s basis vectors. In this case the span will be precisely $W$.
Else, let $y$ be the sum of every permutation of $x$ (counted with multiplicity if necessary), which will be a scalar multiple of $v$, and then the difference $x-y/n!$ will be in $W$. In this case both $V$ and $W$ are spanned, so the span is all of $\mathbb{C}^n$.
Best Answer
Yes, the subspace with $x_2= 0$ is the set or all vectors of the form $\left<x_1, 0, x_3\right>$. The subspace spanned by {<1, 1, 1>, <0, 1, -1>} is the set of all vectors of the form $a\left<1, 1, 1\right>+ b\left<0, 1, -1\right>= \left<a, a+b, a-b\right>$. A vector in the intersection of those must satisfy $x_1= a$, $x_3= a-b$, and $a+ b= 0$. From the last equation, $b= -a$. Then $x_3= a-b= 2a$ so $\left<x_1, 0, x_3\right>= \left< a, 0, 2a\right>= a\left<1, 0, 2\right>$. The intersection of the two subspaces is the one-dimensional subspace spanned by $\left<1, 0, 2\right>$.