How can Kinetic energy formula and the Work formula be derived without assuming the other to be true? After searching how to derive the formula for Kinetic energy, I found that most derivations required the use of the "work" formula. After searching how to derive the work formula for a bit, I found that it required the use of the Kinetic energy formula. This is clearly a circular logic fallacy. Derivations (or at least, convincing arguments) of the kinetic energy formula that didn't require the work formula required relativity to make sense, which is unbelievable considering that Newtonian mechanics were established well before relativity. How in the world did we ever come to a conclusion for the definitions of Work and Kinetic energy if they needed each other? What are the real world definitions of these terms?
 A: When you write:

Derivations (or at least, convincing arguments) of the kinetic energy
  formula that didn't require the work formula required relativity to
  make sense, which is unbelievable considering that Newtonian mechanics
  were established well before relativity.

I assume you are referring to arguments like Ron's argument. Although such explanations may use the word "relativity", they are not referring to Einstein's special relativity from the 20th century, but to Galileo's relativity principle, which he publish before Newton was born. This is an entirely reasonable way to discuss basic Newtonian mechanics because relativity is a fundamental principle there. See https://en.wikipedia.org/wiki/Galilean_invariance
However, the arguments about kinetic energy being derived from work-energy are not circular. The input is Newton's second law, $\mathbf{F} = m \mathbf{a}$.
Suppose a particle has some trajectory $\mathbf{x}(t)$. Then if we evaluate
$$\int_{x_a}^{x_b}\mathbf{F}\cdot \mathrm{d}\mathbf{x} = \int_{t_a}^{t_b} \mathbf{F} \cdot \mathbf{\dot{x}} \mathrm{d}t$$
we get
$$\int_{t_a}^{t_b}m\ddot{\mathbf{x}}\cdot \mathbf{\dot{x}}\, \mathrm{d}t = \int_{t_a}^{t_b} m\frac12\frac{\mathrm{d}}{\mathrm{d}t} \left(\dot{\mathbf{x}}^2\right) \, \mathrm{d}t$$
which is
$$\frac12mv_b^2-\frac12mv_a^2$$
where $v_a = \left|\dot{\mathbf{x}}(t_a)\right|$ and likewise for $v_b$. This is simply kinematics. We can then define the first quantity to be the work done and the last quantity to be the energy, and nothing is circular. From there, we can prove the common introductory physics formulas for other types of energy (e.g. gravitational potential energy) if we assume some knowledge about the forces involved. 
A: $$ m \ddot{\vec{r}} = \vec{F} $$
multiply by $\dot{\vec{r}}$ and integrat over t:
$$ m \int_{t_0}^t \ddot{\vec{r}} \cdot \dot{\vec{r}}~ dt = \int_{t_0}^t \vec{F} \cdot \dot{\vec{r}}~ dt$$
With $\frac{1}{2} \frac{d}{dt} (\dot{\vec{r}}^2) =  \ddot{\vec{r}} \cdot \dot{\vec{r}}$ it follows:
$$ \frac{1}{2} m v^2 + \left( - \int_{t_0}^t \vec{F} \cdot d\vec{r} \right) =  \frac{1}{2} m v_0^2 $$
with $v = |\dot{\vec{r}}(t)|$ and $v_0 = |\dot{\vec{r}}(t_0)|$.
Therefore
$$ E = \frac{1}{2} m v^2 + \left( - \int_{t_0}^t \vec{F} \cdot d\vec{r} \right) $$
is a constant of motion, that is
$$ \frac{d E}{dt} = 0 $$
This holds, wheter or not you call $U = - \int_{t_0}^t \vec{F} \cdot d\vec{r}$ the potential energy at $\vec{r}(t)$ relative to $\vec{r}(t_0)$. Thus energy conservation is a direct consequence of Newton's laws.
A: What about using Galilean free-fall? From $S= \frac 12 g t^2$ and $v = g t$ you get that velocity after a fall $h$ follows $$h= \frac 1{2g} v^2$$ We conclude that if the ball is consuming some essence to get velocity from the line of fall, this essence must be "stored" in space as the square of the velocity. The idea works because if we have already a body falling after a height $h_{01}$ and we allow it to keep falling other distance $h_{21}$, the increase in the square of the velocity will be proportional to the new fall. Say, 
$$ {v_2^2 - v_1^2  \over h_{21}} = {v_1^1 - v_0^2  \over h_{10}} ={v_2^2 - v_0^2  \over h_{20}}$$
Here you see that the argument is purely kinematic, only Galilean formula, not yet newtonian mechanics: in a first idea, not even forces or masses are involved, only some essence of potentiality that translates to actual velocity as the falling body consumes it. 
Both work and energy emanate of this consideration (or its calculus version if you wish, but nothing new appears by using calculus, so I am leaving it for other answers)
If we want to be able to do the argument with dynamics, we add Newton to Galileo and put $g = F/m$. So we get $$h= \frac m{2F} v^2$$
and "work" $$h F = \frac 12 m v^2$$
Or, if we want to do the argument with energies, we simply move the acceleration to the left side in the first formula and multiply by $m$
$$mgh= \frac 1{2} m v^2$$
So, to summarize: the quantity we call "kinetic energy" can be independently related to the product of Force times displacement, $Fh$ above, or to a variation of other quantity, potential energy, $mgh$ in the free fall example. 
The trouble, if any, comes from the potential energy. Here is where the concept of conservative force becomes handy, to be able to use the work formula to recover the potential field from the force field.   
