All finite boolean algebras have an even number of elements?

Yes, a finite boolean algebra with $0\neq 1$ must have an even number of points.

The fact that involution has no fixed points follows from complementation: if $x=x^*$, then $x = x\lor x = x\lor x^* = 1$ and $x=x\land x = x\land x^* = 0$, so $0=1$; hence if $0\neq 1$, then $x\neq x^*$ for all $x$. Since $(x^*)^* = x$, you can partition the algebra into equivalence classes, each with two elements (define $x\sim y$ if and only if $x=y$ or $x=y^*$). So the cardinality of the set, if finite, is even.

Your other conclusion is stronger: you are asserting that every boolean algebra is isomorphic to the full boolean algebra of subsets of a given set $S$, which would mean the number of elements is a power of $2$.

You are also correct that every finite boolean algebra is in fact isomorphic to the boolean algebra of all subsets of a given set $S$, and therefore the number of elements is a power of $2$; but that's a stronger conclusion and does not follow directly merely from the fact that complementation has no fixed points when the algebra has $0\neq 1$.

Here's one way of proving that every finite boolean algebra $B$ is isomorphic to one of the form $2^S$, where $S$ is a set (that is, all subsets of $S$, under $\lor=\cup$, $\land=\cap$, $0=\emptyset$, $1=S$, and ${}^*$ being complementation); the key is to note that in a finite lattice you have certain "minimal elements", and that in a finite boolean lattice, each element is completely determined by the set of minimal elements that are smaller than it.

Let $B$ be a boolean algebra. We define an order on $B$ by $x\leq y$ if and only if $x\land y = x$, or equivalently $x\lor y = y$. With this ordering, $\land$ becomes the greatest lower bound, and $\lor$ the least upper bound.

An element $b\in B$ is called an atom if and only if $b\neq 0$, but if $0\leq x\leq b$, then either $0=x$ or $x=b$; that is, $b$ is an atom if and only if it is a minimal element of $B-\{0\}$.

Now let $x\in B$. I claim that $$x = \lor\{b\in B\mid b\text{ is an atom and }b\leq x\}.$$ Call the least upper bound on the right $a$. Since $x$ is an upper bound for each element of the set, $x\geq a$. Now assume that we do not have $x\leq a$. Then $x\land a^*\neq 0$ (if $x\land a^*=0$, then $x^* = x^*\lor 0 = x^*\lor (x\land a^*) = (x^*\lor x)\land (x^*\lor a^*) = x^*\lor a^*$, and taking complements we get $x = x\land a$, hence $x\leq a$). So there exists an atom $b$ such that $b\leq x\land a^*$. But then $b\leq a$ (since $b$ is an atom and $b\leq x$) and $b\leq a^*$ by assumption, so $b\leq (a\land a^*) = 0$, which is impossible (since $b\neq 0$). This contradiction arises from the assumption that $x\not\leq a$, so $x\leq a$; since $x\geq a$, we conclude that $x=a$.

Thus, each element is characterized by the set of atoms that are less than or equal to it. We can define a boolean algebra homomorphism $$f\colon B \to \mathcal{P}(A(B)),$$ where $A(B) = \{b\in B\mid a \text{ is an atom}\}$, by $$f(x) = \{b\in A(B)\mid x\leq b\}.$$ and using the fact above it is straightforward now to show that $f$ is indeed a bijective boolean algebra isomorphism.

The more general statement that every boolean algebra is isomorphic to a subalgebra of the field of subsets of some $X$ depends on your Set Theory; it follows from the Boolean Prime Ideal Theorem (every ideal in a boolean algebra can be extended to a prime ideal), which is known to be strictly weaker than the Axiom of Choice, but not provable in ZF. (It is considered a weak form of the Axiom of Choice). (Note that you have to specify "subalgebra"; you cannot hope for every boolean algebra to be the full algebra of subsets of a given $X$, because that would imply that there are no infinite countable boolean algebras, which is false.)

Yes, any finite Boolean algebra is isomorphic to a field of sets, so has $2^n$ elements for some $n$. You can prove the latter fact using the fact that any Boolean algebra is in particular a vector space over the finite field $\mathbb{F}_2$ (vector addition is given by XOR). Any finite-dimensional such vector space is isomorphic to $\mathbb{F}_2^n$, hence has $2^n$ elements.

In fact, any Boolean algebra is isomorphic to a field of sets. This is a consequence of Stone's representation theorem.

(Also, there's no reason to exclude the trivial Boolean algebra. It's the collection of subsets of the empty set!)