In every source I find discussing Lindenbaum algebras, it seems that an algebra induces operations on the elements of the Lindenbaum algebra. For instance, in propositional calculus on $X=\{x_1, x_2\}$, then if $a$ and $a'$ are provably equivalent, and so are $b$ and $b'$ then $a \implies b$ and $a' \implies b'$ are provably equivalent so that if $\bar{a}$ denotes the element of the lindenbaum algebra $L[X]$ that is the equivalence class of $a$ then by defining \begin{equation*}\tag{1}\bar{a} \implies \bar{b} = \overline{a \implies b}\end{equation*} we can turn $L[X]$ into a boolean algebra. My question is whether we can start with an arbitrary logic and still define the Lindenbaum algebra in this way.
For example, if we take propositional calculus and take 2 elements $a, b$ in the free propositional algebra on X such that $a \vdash b$ and $b \vdash a$. We chose proofs $A$ and $B$ of these entailments and define a new logic consisting of the set and valuations from propositional logic on $X$. But as the set of proofs we use just $\{A, B\}$. Now, (1) is not true? So for this logic is there still a canonical representation of the Lindenbaum algebra?
And what if the set is even more general and is not an algebra itself? We could still define valuations and proofs, but then what sort of algebra would be the Lindenbaum algebra, how can the Lindenbaum algebra's operations be induced by operations in the starting algebra if there is no starting algebra? Perhaps I am just totally confused by the whole concept?
I don't quite understand your proposed counterexample, but it's certainly true that there are logics with non-truth-functional operators (e.g. modal logic) and these make Lindenbaum algebra constructions more nuanced. A more general notion of equivalence is the Leibniz congruence: informally, given a logic $\mathcal{L}$ and a theory $T$ in $\mathcal{L}$, two sentences $\varphi,\psi$ are $\Omega(T)$-equivalent iff $\varphi$ and $\psi$ are indistinguishable by $\mathcal{L}$ given $T$. A formal definition of $\Omega(T)$ can be found at wikipedia; Blok/Pigozzi's book Algebraizable logics is a quite nice introduction to the topic. The general theme is that under very mild (but not quite trivial!) hypotheses we can indeed construct a nice analogue of the classical Lindenbaum algebra.