Complement of regular language is regular

There is also an algebraic characterization of regular languages. A language $L\subset \Sigma^*$ is regular iff it exists an homomorphism (of monoids) $\phi : \Sigma^*\rightarrow M$ with $M$ a finite monoid and $$ L=\phi^{-1}(S) $$ where $S\subset M$. You end using the formula $\phi^{-1}(\bar{S})=\overline{\phi^{-1}(S)}$.

This is an interesting question. I interpret your requirements as giving a proof of the closure under complement dealing only with regular expressions. But there is no such proof.

Short answer. Such a proof would give a proof that in any monoid, the set of rational subsets is closed under complement. However this is not true, for instance in the monoid $a^* \times \{b,c\}^*$: see this page for a short proof.

Details.

Recall that a monoid is a set $M$ equipped with an associative operation (denoted multiplicatively) and an identity element $1$. Then $\mathcal{P}(M)$, the set of subsets of $M$, is equipped with an addition, the usual set union (that is $X + Y = X \cup Y$ by definition), and a product: $XY = \{xy \mid x \in X, y \in Y \}$. Finally, if $X$ is a subset of $M$, then $X^*$ is the submonoid of $M$ generated by $X$. Note that $X^* = \{1\} + X + X^2 + \cdots\ $ The set of rational subsets of $M$ is the smallest subset of $\mathcal{P}(M)$ containing the singletons $\{m\}$ (for $m \in M$) and closed under the three operations sum, product and star. As you can see, in the case of a free monoid, you recover the usual notion of regular language.

By the way, the notion introduced by Gérard Duchamp in his answer also extends to any monoid: a subset $X$ of a monoid $M$ is recognizable if there exists a monoid morphism $\varphi$ from $M$ onto a finite monoid $F$ and a subset $P$ of $F$ such that $\varphi^{-1}(P) = X$.

Now, Kleene's theorem implies that in a free monoid, a subset is rational if and only if it is recognizable. However, this equivalence does not hold in any monoid: for instance in $\mathbb{Z}$, $\{0\}$ is rational but not recognizable. It is more difficult to find examples for which the rational sets are not closed under intersection (and hence under complement), but an example is given in the short answer.