You don't quite have the right notion of isomorphism between relational structures; rather, an isomorphism needs to preserve and reflect each relation in question. A relation on the left has to hold iff it holds on the right.
In full generality - and this is the notion of isomorphism coming from model theory - an isomorphism between two structures $\mathcal{A}$ and $\mathcal{B}$ in the same language consisting of some relation symbols and some function symbols (thinking of constant symbols as $0$-ary function symbols) is a map $I:\mathcal{A}\rightarrow\mathcal{B}$ such that:
$I$ is a bijection.
For each $n$-ary function symbol $f$ in the language and each $a_1,...,a_n\in\mathcal{A}$, we have $$I(f^\mathcal{A}(a_1,...,a_n))=f^\mathcal{B}(I(a_1),...,I(a_n)).$$
For each $k$-ary relation symbol $R$ in the language and each $a_1,...,a_k\in\mathcal{A}$, we have $$R^\mathcal{A}(a_1,...,a_k)\iff R^\mathcal{B}(I(a_1),...,I(a_k)).$$
Note that we're distinguishing between function/relation symbols ($f, R$) and the actual functions/relations in the structures they name ($f^\mathcal{A},f^\mathcal{B},R^\mathcal{A},R^\mathcal{B}$). This can often feel tedious at first, but it's important (although down the road once well-understood the distinction can be elided).
Now as to the "relationalization" process, you have the right idea but your implementation is not ideal. Specifically, your process for going from a functional language to a relational language is "structure-dependent:" exactly how many new relation symbols we introduce depends on the structure in question, so it's not a uniform change of language across all structures.
However, your basic idea is absolutely correct: you want to keep track of the "basic facts" of the form "This tuple of elements gets sent to that element" in a relational way. The right way to do this is via the graph of a function: given an $n$-ary function $f$ on some set $X$, the graph of $f$ is the $(n+1)$-ary relation on $X$ given by $$\{(x_1,...,x_n,x_{n+1})\in X^{n+1}: f(x_1,...,x_n)=x_{n+1}\}.$$ (Indeed, in the usual set-theoretic formalism a function literally is its graph, but that's getting a bit needlessly "under-the-hood.")
So in general we "relationalize" a language by replacing each $n$-ary function symbol $f$ with an $(n+1)$-ary relation symbol $Graph_f$, and we "relationalize" a structure in this language by interpreting $Graph_f$ as the graph of the interpretation of $f$. We then have:
Two structures are isomorphic iff their relationalizations are isomorphic.
I'm going to answer in terms of ZF set theory since that is what most of us need.
In ZF, there is no definition for a set. It is a primitive idea. All you have is the notion set and membership and that gives you equality of sets, and in turn equality of members.
Whether or not two elements of a set are equal is again a matter of set equality. You don't need anything extra to tell you when two elements are equal.
It certainly can't be part of the definition of a set, because an equivalence relation is essentially a special subset of $X\times X$, and if you haven't accepted what a set is yet, you shouldn't be discussing thing like subsets of $X\times X$. You will just be going around in circles.
You can grant $X$ an equivalence relation given by the partition of the set into singletons, so that you get the "identity relation", but it doesn't tell you anything new.
E.g., can we call equinumerous sets isomorphic?
Sure you can. In the category of sets, the isomorphisms are precisely the bijections. There are "isomorphic in the category of sets."
You don't need operations to do this... a category can be made up of non-algebraic objects. That is isomorphism and homomorphism are not algebraic-only concepts.
Thus, every set by the definition is an algebraic structure with the identity operation.
It would be more plausible to say that a set is an algebraic structure with no operations. I don't know if universal algebra accepts this empty case, but they may.
Best Answer
As far as I am aware, there is no name for such a structure, so I will simply call it a permutation. I think there is little use in group theory for allowing infinite permutations to be cyclic, whereas allowing the infinite group $\mathbb{Z}$ to be cyclic is useful for the classification of finitely generated abelian groups. Nonetheless, one could certainly extend the definition of a cyclic permutation to be a permutation $\sigma:X\to X$ such that there exists $x_0\in X$ such that for all $x\in X$ either there exists $n\in\mathbb{Z}$ such that $\sigma^n(x_0)=x$, or $\sigma(x)=x$ (i.e. there is at most one orbit which has more than one element). The "or $\sigma(x)=x$" could be removed to better match the definition of a cyclic group as something which is generated by one element, but the traditional definition of cyclic permutation requires this caveat. I will call $\sigma$ primitive cyclic if the "or $\sigma(x)$" condition can be dropped (i.e. there is exactly one orbit).
In the class of permutations, appending two disjoint permutations together corresponds to a coproduct (i.e. disjoint union) in the category of these algebraic objects. As far as I am aware, there is not too much we can say about this category since permutations are a fairly simple algebraic object, but we do get one theorem analogous to the fundamental theorem of finitely generated abelian groups. Namely, any finitely generated permutation (or even non-finitely generated permutations for that matter) can be decomposed into a coproduct of primitive cyclic permutations.
$\textit{Proof}.$ Let $\sigma:X\to X$ be a permutation. We can define an equivalence relation by declaring $x\sim y$ iff there exists $n\in\mathbb{Z}$ such that $y=\sigma^n(x)$ (i.e. the equivalence class of $x$ is the subpermutation of $(X,\sigma)$ generated by $x$). For each equivalence class, choose a representative and denote the collection of these representatives by $\{x_\alpha\}_{\alpha\in I}$. I claim
$$(X,\sigma)\cong\coprod_{\alpha\in I}\langle x_\alpha\rangle$$
where $\langle x_\alpha\rangle$ denotes the substructure of $(X,\sigma)$ generated by $x_\alpha$ which is clearly a primitive cyclic permutation. Let $\iota_\alpha:\langle x_\alpha\rangle\to X$ be the inclusion maps (which are clearly homomorphisms between these algebraic structures), let $\tau:Y\to Y$ be a permutation, and let $f_\alpha:\langle x_\alpha\rangle\to Y$ be a collection of homomorphisms (i.e. functions such that $\tau f_\alpha=f_\alpha\sigma\vert_{\langle x_\alpha\rangle}$). Then we can define a function $f:X\to Y$ as such: Given $x\in X$, there exists a unique $\alpha\in I$ such that $x\in\langle x_\alpha\rangle$, so take $f(x):=f_\alpha(x)$. By uniqueness of $\alpha$, this is well-defined, and because $\tau f_\alpha=f_\alpha\sigma\vert_{\langle x_\alpha\rangle}$ for all $\alpha$, we see $\tau f=f\sigma$ (i.e. $f$ is a homomorphism). Furthermore, we clearly see $f_\alpha=f\iota_\alpha$ for every $\alpha$. Thus, $(X,\sigma)$ satisfies the universal property of the coproduct, so there is a canonical isomorphism between $(X,\sigma)$ and $\coprod_\alpha\langle x_\alpha\rangle$.