As pointed out by Snowball, the problem is inherently hard, see also this paper.
However, it can be done much faster in general than generating all the codewords.
I explain the idea for linear $[n,k]$ codes $C$ with $n = 2k$.
First, we construct two generator matrices $G_1 = (I\ A)$ and $G_2 = (B\ I)$ of $C$ where $I$ is the $(k\times k)$ unit matrix and $A,B$ are two $(k\times k)$ matrices. This is only possible if the positions $1,\ldots,k$ and $k+1,\ldots n$ form two information sets of $C$. If this is not the case, we have to find a suitable coordinate permutation first.
Now a codeword of weight $w$ has weight at most $\lfloor w/2\rfloor$ either in the first or in the second $n$ coordinates.
Thus, we can find all codewords of weight $\leq w$ among the codewords $x G_1 = (x, xA)$ and $x G_2 = (Bx, x)$, where $x$ is a vector of length $k$ and Hamming weight at most $\lfloor w/2\rfloor$.
So we can find the minimum distance $d$ of $C$ if we do this iteratively for all $w = 1,2,3,\ldots, d$.
In this way, you have to generate only a small fraction of all the codewords to find the minimum distance, and the idea can be generalized to any linear code. The first step then is to find a covering of the coordinates with information sets. However, the algorithm is still exponential, of course.
The webpage codetables.de is a valuable source for bounds on the best known minimum distances for fixed $q$, $n$ and $k$.
You can always first check what the BCH-bound gives you.
It is known (and easy to check) that the irreducible polynomial $p(x)=x^6+x+1$ is primitive. In other words $n=63$ is the smallest integer such that $p(x)\mid x^n-1$. If $\alpha\in\Bbb{F}_{64}$ is a zero of $p(x)$ then by Galois theory of finite fields so is $\alpha^2$. Of course, $\alpha^0$ is a zero of the factor $x+1$.
IMO the key to this exercise is that the third factor is the reciprocal polynomial of $p(x)$, that is
$$
\tilde{p}(x)=x^6+x^5+1=x^6p(\frac1x).
$$
From this we see immediately $\alpha^{-1}$ and $\alpha^{-2}$ are zeros of the factor $\tilde{p}(x)$.
So we have shown that $\alpha^j$ is a zero of the generator polynomial polynomial for five consecutive values of $j=-2,-1,0,1,2$. The BCH-bound then tells us that the minimum distance of the code is at least $5+1=6$. I leave it to you to verify that the generator polynomial is itself of weight six. We can thus conclude that the minimum distance of this code is $d_{min}=6$.
It may be worth observing that because $x+1$ is a factor of the generator, all the codewords have $x=1$ as a zero. Therefore they must have an even weight.
Best Answer
It's difficult in general to get the free distance. By inspection, we can find that, restricting to the first row of the generator matrix, the transitions that take us out from the zero state and the one that returns to it correspond to the encodings:
$$\cdots 000001 \cdots \to \cdots |1011|\cdots$$ $$\cdots 100000 \cdots \to \cdots |0110|\cdots$$
Then, restricing always to the first branch, the amount of ones that a "finite" non-zero sequence produces is at least five. And this is reachable by simply placing a single one at the input.
Then, the (full) input sequence corresponding for a single one in the first branch, and all zeros in the second, produces an (full) output of weight five.
That there is no other output sequence with less weight produced by the second branch can be seen by considering the (necessary) transitions $$\cdots 00001 \cdots \to \cdots |0111|\cdots$$ $$\cdots 10000 \cdots \to \cdots |1101| \dots$$
Hence the free distance is $5$