I know that the notion of "set" is one that cannot be defined mathematically since it is the fundamental data type that is used to define everything else (and the definition which says that "sets" are the objects in any model of set theory is to me circular since models are defined in terms of sets).
It seems to me that there is another fundamental concept just like "set", namely the notion of a "variable". Is this true?
On
dtldarek has given an answer from one point of view. Let me offer another.
A variable in mathematics often means an element in something (a ring, a group, a vector space, ...) which can be specialized to some more specific value.
In modern algebra, this notion becomes formalized in various ways, one of which is by the notion of the free object on (wikipedia say "over", but my own experience is that it is more common to speak of the free object "on") a particular set of variables.
If you haven't seen it before, this notion will probably seem quite abstract (like a lot of formalism the first time you see it!). But it actually provides a rather precise formal match with the intuitive notion of a variable.
Added in response to the OP's comment: E.g. the polynomial ring $\mathbb C[x_1,\ldots,x_n]$ is the free commutative $\mathbb C$-algebra in the variables $x_1,\ldots,x_n$. If $A$ is any other commutative $\mathbb C$-algebra (e.g. $\mathbb C$ itself), then giving a homomorphism $\mathbb C[x_1,\ldots,x_n] \to A$ is the same as choosing $n$ elements $a_1,\ldots,a_n \in A$ ("the values of the variables") and declaring $x_1\mapsto a_1,\ldots, x_n \mapsto a_n$.
This illustrates the general principal that the free object (in some particular context) on the variables $x_1,\ldots,x_n$ is an object in which no relations are imposed between the elements $x_1,\ldots,x_n$, and so it can be mapped to any other object (of the appropriate sort) just by choosing values of the variables $x_1,\ldots,x_n$ in that object.
Variations of this point of view are how idea about variables and equations between them are implemented in contemporary algebraic geometry, for example.
In pure mathematics there is no such thing as variable, there are only constants. Consider equality $a = 5$. This supposed "variable" isn't variable at all!
On the other hand, there are those curious letters in the formulas, what do they mean you ask? Well, those are informal expressions that describe the objects we reason about, however, they do not have any precise meaning, they are not formal. It doesn't contradict that the description of the object might be perfectly fine, after all you use natural language to describe the notion of set, don't you?
Still, there is a way of formalizing this and the domain which happens to deal with such problems is called semantics, where there actually is something that is called a variable, but all the formal derivations are usually long, tedious and cumbersome. Moreover semantics is more about computer science, where the precise meaning of an expression is important for the computer that is to evaluate it (it doesn't know anything about our informal notion of variable, so we need to explain everything in the tiniest details).
In mathematics we deal with those informal expressions and "pattern-match" them with suitable cases. If you do it properly, everyone knows what do you mean (i.e. what function you want to define, etc.) so there is no need to overformalize it.
I know what I wrote looks more like a peculiar fairytale than a concrete answer, but that's the way I understand it. Hope that helps, even if only a bit ;-)