We can do it in $32$ tries as follows:
\begin{align}
\begin{matrix}
111 & 222 & 333 & 444 \\
123 & 142 & 134 & 243 \\
231 & 214 & 341 & 432 \\
312 & 421 & 413 & 324
\end{matrix}
&&
\begin{matrix}
555 & 666 & 777 & 888 \\
567 & 586 & 578 & 687 \\
675 & 658 & 785 & 876 \\
756 & 865 & 857 & 768
\end{matrix}
\end{align}
The idea is that the first block of $16$ rules out all combinations with at least two numbers from $\{1, 2, 3, 4\}$ and the second block of $16$ rules out all combinations with at least two numbers from $\{5, 6, 7, 8\}$. By Pigeonhole Principle, any combination must have two numbers in one of these two sets, so we have covered all possible combinations.
Proof of Optimality
Assume on the contrary that $31$ tries are sufficient.
Lemma: For any position and any number $n \in \{1, 2, \ldots , 8\}$, we must have tried $\geq 3$ combinations with $n$ in that position.
Proof: By symmetry, it suffices to show that we must have tried $\geq 3$ combinations starting with $1$.
Assume on the contrary that at most two of the combinations tried start with $1$, then each rules out $15$ combinations starting with $1$, so we still have $64-2(15)=34$ possible combinations starting with $1$. All other combinations tried do not start with $1$, hence only rule out one combination starting with $1$, so we need to try at least $34$ more combinations, a contradiction.
Therefore we must have tried $ \geq3$ combinations starting with $1$.
If for each $n=\{1, 2, \ldots , 8\}$, we have tried $\geq 4$ combinations starting with $n$, then we require at least $32$ tries, a contradiction. Therefore for some $n$, we have tried at most $3$ combinations starting with $n$, hence by the lemma we have tried exactly $3$ combinations starting with $n$.
Now WLOG assume that $n=1$, by symmetry. So we have something like
$$\begin{matrix} 1ab \\ 1cd \\ 1ef \end{matrix}$$
where $a, b, c, d, e, f$ need not be distinct.
Note that all combinations of the form $1xy$ where $x \not =a, c, e$ and $y \not =b, d, f$ have not been ruled out.
If $a, c, e$ are not pairwise distinct, then there are at least $6$ choices for $x$, and there are at least $5$ choices for $y$, so we have $30$ combinations starting with $1$ which have not been ruled out. All other combinations we try do not start with $1$, hence rule out at most one of these $30$ combinations. Thus we need $\geq 30$ more combinations, making a total of $33$, a contradiction.
Therefore $a, c, e$ are pairwise distinct. Then there are $5$ choices for $x$ and at least $5$ choices for $y$, so there are $25$ combinations of the form $1xy$ which have not been ruled out, so we require $\geq$ $25$ combinations of the form $nxy$ (where $n \not =1$) to rule these out. That gives $28$ combinations tried so far.
Now note that by the lemma, we need to try at least $3$ combinations with $a$ in the middle, and we currently only have one such combination $1ab$ (all the $nxy$ combinations have $x \not =a$). Thus we need to try two more combinations with $a$ in the middle. Similarly, we need to try two more combinations with $c$ in the middle, and two more with $e$ in the middle, giving a total of $34$ combinations tried, a contradiction.
We conclude that we require at least $32$ tries, and this is indeed minimal by our construction at the start of the post.
Best Answer
We want to find a word over the alphabet $\{1,\ldots,n\}$ that is as short as possible and contains all $n!$ permutations of the alphabet as infixes. Let $\ell_n$ denote the shortest achievable length. Clearly, $$\tag1\ell_n\ge n!+(n-1).$$ Of course, $(1)$ is somewhat optimistic because it requires $(n-1)$-overlaps between all consecutive permutations, but that is only possible for cyclicly equivalent permutations. As there are $(n-1)!$ equivalence classes under cyclic equivalence, and switching between these requires us to "waste" a symbol, we find that $$\tag2\ell_n\ge n!+(n-1)+(n-1)!-1=n!+(n-1)!+(n-2).$$ In particular, inequality $(2)$ is sharp for the first few cases $\ell_1=1$, $\ell_2=3$ (from "121"), $\ell_3=9$ (from "312313213"). However, it seems that that $\ell_4=33$ (from "314231432143124313421341234132413").
Feeding these few values into the OEIS search engine reveals http://oeis.org/A180632 and we see that the exact values seem to be known only up to $\ell_5=153$ (which is your original problem)! Quoting the known bounds from there, we have $$ \ell_n\ge n! + (n-1)! + (n-2)! + n-3$$ (which can supposedly be shown similarly to how we found ($2)$ above) and $$\ell_n\le \sum_{k=1}^nk!.$$ These bounds tell us that $152\le l_5\le 153$, but it has been shown in 2014 that in fact $\ell_5=153$. The next case seems to be still open: The inequalities only tell us $867\le \ell_6\le 873$, but another result of 2014 shows that $\ell_6\le 872$.