As in the link of Gerry, one is supposed to check if there are any algebraic integers among the seven :$\Sigma_{i=0}^2 a_i \alpha^i/2$, where $a_i$ are either $0$ or $1$, and not all of them are $0$.
Now, after some computations(some minutes maybe), one finds that the only one among them which is an algebraic integer is: $(\alpha+\alpha²)/2$, satisfying the irreducible polynomial: $x^3-x²-3x-2$.
Replace $\alpha²$ by $(\alpha+\alpha²)/2$ in the basis, one then finds that the discriminant becomes $-107$ by the transition formula. Hence this is an integral basis, as required.
P.S. Since this is subject to a certain amount of calculations, of which I think quite tediously, it is quite expectable that some errors penetrated in the above arguments. Thus, if there are some mistakes, please tell me. Thanks in advance.
Can you show that $|\Delta(x_1,\dots,x_n)|$ is minimal amongst all integers? If so, suppose that this isn't an integral basis, so that there is some $\alpha\in\mathfrak{O}_K$ such that $\alpha=b_1x_1+\cdots+b_nx_n$, for $b_1,\dots,b_n\in\mathbb{Q}$, but at least one is not in $\mathbb{Z}$, say $b_1\notin\mathbb{Z}$. Then $b_1=b+r$, where $b\in\mathbb{Z}$, and $0<r<1$, and we can construct a new set of integers, $y_1=\alpha-bx_1$, and $y_i=x_i$, for $i=2,\dots,n$. Can you then show that $|\Delta(y_1,\dots,y_n)|<|\Delta(x_1,\dots,x_n)|$?
Edit. Sorry, scratch the method I was thinking of. Although I still think that you can do it that way, it would be considerably more involved than I think is necessary.
Let $G=\mathbb{Z}x_1+\cdots+\mathbb{Z}x_n\subseteq\mathfrak{O}$. Clearly $x_1,\dots,x_n$ span $K/\mathbb{Q}$, so we can write $\alpha=b_1x_1+\cdots+b_nx_n$, for some $b_1,\dots,b_n\in\mathbb{Q}$. Write each $b_i=c_i+r_i$, where $c_i\in\mathbb{Z}$, and $0\le r_i<1$. Then
$$
\alpha-\underbrace{c_1x_1+\cdots+c_nx_n}_{\in~G}=r_1x_1+\cdots+r_nx_n
$$
Now look at the coefficients of the powers of $\theta$, and don't forget that $[\mathfrak{O}_K/\mathbb{Z}[\theta]]$ divides $d$.
Best Answer
No. Take for instance $\alpha = \sqrt 5$.
Even worse, there may not exist a suitable $\alpha$. This is the case for the cubic field generated by a root of the polynomial $X^{3}-X^{2}-2X-8$, according to Wikipedia. For a discussion and a proof, see Rings of integers without a power basis by Keith Conrad.