Making my comment an answer.
There are in fact formulations of Set Theory using purely Category Theory. One famous is given by W. Lawvere's $\sf ETCS$ (Elementary Theory of Category of Sets) which was also one of the first attempts of basing Set Theory on Category Theory (a revised version of his original paper can be found here). Of course, then you have to define the concepts of Category Theory without ever mention sets. This is doable, even though a little tedious, see for example single-sorted defintion of categories in nLab (which cites S. Mac Lanes "Categories for the working mathematician" as source, chapter I.$1$ in particular).
The key idea behind Lawvere's paper is to formalize how sets and, especially, functions maps between sets (i.e. functions) behave instead of arguing how sets look like from inside (roughly). Thus, $\sf ETCS$ is an external set theory (or structuralistic) in contrast to, lets say $\sf ZFC$ which is an internal set theory (or materialistic). For a more recent approach towards Lawvere's $\sf ETCS$ see also T. Leinster's "Rethinking Set Theory" which tries to capture the essence of Lawvere's idea in more intuitive terms.
Speaking about foundations: actually,$\sf ZFC$ and $\sf ETCS$ are nearly equiconsistent (i.e. are both able to prove exactly the same things). By nearly I refer to the fact the $\sf ETCS$ is weaker in so far that there is no analogue of the Axiom Schema of Replacement. Adding a variant of this axiom, however, yields to the two theories being equiconsistent. (EDIT (as pointed out by jgon): this is not like replacing Set Theory by Category Theory in foundational matters but more like describing the fundamental principles in a different language).
That we can represent nearly every mathematical strcuture in terms of sets stems from the fact that many structures are in fact defined as sets with extra structure (this is especially true for algebraic structures such as groups, rings, fields, etc.). But we can also view these as objects of their respective categories, where the categories carry the information making them special (for example, the category of groups does have a zero object, while the category of sets does not). Currently I cannot think of a mathematical concepts that is not describable via sets/categories but I might be missing something out.