Aha! Here we go.

Just use Ryser's formula exactly as is, but be clever not to redo work you've already done. If it's an $n \times n$ matrix with $F$ distinct columns, you'll be able to compute its permanent in time roughly $F n^{1+F}$ ish (which would be great if you can get $F$ down).

**More details:**

Recall Ryser's formula is

$$\text{perm}(A) = (-1)^n \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i=1} ^{n} \sum_{j \in S} a_{i,j}.$$

The problem is that if we don't do anything clever, then there are too many terms of this sum. But! In our case, *many of these terms are equal*. The thing we're adding up depends on $S$, but it actually just depends on how many columns of each type are in $S$. [If this is already clear, then don't bother reading the rest]

Let's say that the distinct columns of $A$ are $\vec{x}^{(1)}, \vec{x}^{(2)}, \ldots , \vec{x}^{(F)}$ and that $\vec{x}^{(j)}$ appears $f_j$ times. Then the above sum is equal to

$$\text{perm}(A) = (-1)^n \sum_{(s_1, s_2, \ldots, s_F)}(-1)^{s_1 + s_2 + \cdots + s_F} \prod_{j=1} ^{F} {f_j \choose s_j} \prod_{i=1} ^{n} \sum_{k = 1} ^{F} s_k \vec{x}^{(k)} _{i},$$

where the sum is taken over all non-negative vectors [summing to at most $n$, where each coordinate $s_i$ is at most $f_i$]. A crude bound is that there are at most $\mathcal{O}(n^F)$ such terms, giving this a running time of at most like $\mathcal{O}(n^{F+1} F)$ or whatever.

Of course, this doesn't use anything about what the columns look like (and the above sum might be easier to compute than just adding up each term). But it's a start.

**(Added as per suggestion) Working out $F=3$** Suppose we are in the optimistic case that the matrix has $n$ columns but only $3$ distinct columns. Let's call these columns $\vec{x}, \vec{y}$, and $\vec{z}$, and suppose each appears $f_x, f_y,$ and $f_z$ times (respectively). [So we have $f_x + f_y + f_z = n$]

Then we have

$$\text{perm}(A) = (-1)^n \sum_{(a, b, c)}(-1)^{a+b+c} {f_x \choose a} {f_y \choose b} {f_z \choose c} \prod_{i=1} ^{n} (a \vec{x}_{i} + b \vec{y}_i + c \vec{z}_i),$$

where the sum is taken over all triples $(a,b,c)$ summing to at most $n$.

Said slightly differently, for a vector $\vec{u} \in \mathbb{R}^n$, let $V(\vec{u}) = u_1 u_2 \cdots u_n$ be the product of its coordinates. [So $V(\vec{u})$ is the (signed) volume of the axis-parallel box with one corner at the origin and an antipodal corner at $\vec{u}$] Then the above formula is just
$$\text{perm}(A) = (-1)^n \sum_{(a, b, c)}(-1)^{a+b+c} {f_x \choose a} {f_y \choose b} {f_z \choose c} V(a \vec{x} + b \vec{y} + c \vec{z}),$$
which looks a little nicer to me and feels more geometric. [I'm then tempted to write this linear combination as a product of a matrix and the vector $(a,b,c)$, but let's not]

(If you'd like me to sketch some code or work out an example or something, lemme know)