Can we treat logic mathematically without using logic? I'm reading Kleene's introduction to logic and in the beginning he mentions something that I have thought about for a while. The question is how can we treat logic mathematically without using logic in the treatment? He mentions that in order to deal with this what we do is that we separate the logic we are studying from the logic we are using to study it (which is the object language and metalanguage, respectively). How does this answer the question? Aren't we still using logic to build logic? 

And I have a feeling that the answer is to some extent that we use simpler logics to build more complex ones, but then don't we run into a paradox of what 's the simplest logic, for won't any system of logic no matter how simple be a metalanguage for a simpler language?
We use logic to study logic, not to create logic.  Our study is usually not intended to justify some logic but rather to understand how it works. For example, we might try to prove that, whenever a conclusion $c$ follows from an infinite set $H$ of hypotheses then $c$ already follows from a finite subset of $H$. Many logical systems have this finiteness property; many others do not. And that's quite independent of the logic that we use in studying this property and trying to prove or disprove it for one or another logical system.

Here's an analogy: Suppose a biologist is writing a paper about the origin of trees.  He could use a wooden pencil to write the paper.  That pencil was made using wood from trees, so its existence presupposes that the origin of trees actually happened.  Nevertheless, there is nothing circular here.  The pencil that is being used probably consists of wood quite different from that in prehistoric trees.  And even if it wasn't different, there's no problem with using the pencil to describe those ancient trees.  

Similarly, there's no problem using ordinary reasoning, also called logic, to describe and analyze the process of reasoning.
You can use arithmetics to do logic.

true is 1

false is 0

$a \cdot b \Leftrightarrow$ logical and

$1-a \Leftrightarrow$ logical not

$a+b&gt;0 \Leftrightarrow$ logical inclusive or

$a+b=1 \Leftrightarrow$ logical exclusive or