What can be known about the formulas for energy only from the fact that it is conserved? The question is to figure out how the energy can be derived knowing just one thing:

There is a quantity called Energy that is conserved over time.

The goal is to get an equation that somehow implies the basic formulas for kinetic energy and potential energy, $\frac{1}{2}mv^2$ and $mgh$. So how can we get this with just a rudimentary knowledge of physics and algebra, and the first principle (stated above)?
 A: Let $E$ denote a quantity that does not change over time (from the first principle). 
Consider a ball with mass $m$ dropped from a height $h$. As the ball drops, its speed changes due to the gravitational acceleration $g$, reaching a final value $v$ at impact. Thus, we can infer that the quantity $E$ depends on these 4 parameters: $$E(m,H,g,V)$$
where $H$ is a variable height and $V$ is a variable velocity. 
Now, consider the ball during the instant that it's dropped. It has height $h$ and $V=0 $.
Then consider the ball right before it hits the ground. It has $H=0$ and velocity $v$.
Thus, the velocity $v$ and height $h$ are most likely not multiplied by each other, as it would give a value of $0$ both at the top and at the bottom. So, from the first principle:$$E_i(m,h,g,0)=E_f(m,0,g,v)$$ $$E_i(m,h,g)=E_f(m,g,v)$$
The initial energy, which has no dependence on velocity, and complete dependence on the object's height above the ground, can be called the potential energy. Likewise, the final energy, which is completely dependent on the object's velocity, may be called the kinetic energy.
We see that $m$ has units of mass $\left(M\right)$, $h$ has units of length $\left(L\right)$, $g$ has units of length over time squared $\left(\frac{L}{T^2}\right)$, $v$ has units of length over time $\left(\frac{L}{T}\right)$. So we can use dimensional analysis to figure out how these parameters most likely fit into the equation:
$$\alpha m^ah^bg^c=\beta m^dg^ev^f$$
$$M^aL^b \left( \frac{L}{T^2} \right)^c=M^d\left( \frac{L}{T^2} \right)^e \left( \frac{L}{T} \right)^f$$
$$M^aL^{b+c}T^{-2c}=M^dL^{e+f}T^{-2e-f}$$
( $\alpha$ and $\beta$ are constants of proportionality, and are dimensionless.)
We end up with the following system of equations, which has 3 equations and 6 unknowns:
$$a=d$$ $$b+c=e+f$$ $$-2c=-2e-f$$
If we let $a=w$, $b=u$, and $c=v$, then we have:
$a=w$
$b=u$
$c=v$
$d=w$
$e=v-u$
$f=2u$
So we have the following general equation:$$\alpha m^wh^ug^v=\beta m^wg^{v-u}v^{2u}$$
It isn't clear at this point whether or not the mass $m$ is relevant to the energy; since it appears on both sides of the equation, it's safe to remove it for now. Also, we could remove the constants $\alpha$ and $\beta$, keeping in mind that they're still there. So the reduced form of the equation is: $$h^ug^v=g^{v-u}v^{2u}$$
It's clear that for any $u$ and $v$ that we choose, the equation would satisfy our dimensional analysis. So, the only thing left to do is input values for $u$ and $v$ and see what kind of equations we can come up with.
For $u=0$, $v=1$
$$g=g$$
For $u=1$, $v=0$
$$h=g^{-1}v^2$$
$$hg=v^2$$
For $u=1$, $v=1$
$$hg=v^2$$
For $u=1$, $v=2$
$$hg^2=gv^2$$
$$hg=v^2$$
For $u=2$, $v=2$
$$h^2g^2=v^4$$
$$hg=v^2$$
Interestingly, for any $u$ and $v$ that we choose, the equation remains unchanged. (I was shocked when I saw this!) At this point, it isn't clear whether the potential energy, the kinetic energy, or both depend on the gravitational acceleration.
At this point I would like to move on to another example where a block of mass $m$ and velocity $v$ is on a frictionless surface and compresses a spring with spring constant $k$ by an amount $x$. We can infer that $E$ depends on these 4 parameters:
$$E(m,V,k,X)$$
where $V$ is a variable velocity and $X$ is a variable amount of compression in the spring.
Now, consider the block before it begins compressing the spring. It has velocity $v$ and $X=0$. 
Then consider the block when it fully compresses the spring. It has $v=0$ and compression in the spring is $x$. By the same logic as above, I deduce that the velocity and compressed length cannot be multiplied by each other at any instant in time to get the quantity $E$. We can write the following equation from the first principle:
$$E_i(m,v,k,0)=E_f(m,0,k,x)$$ $$E_i(m,v,k)=E_f(m,k,x)$$
The final quantity may be called the spring potential energy. The initial quantity in this equation is equivalent to what we called the kinetic energy in the first example. However, this quantity does not depend on $g$ while the term that we called the kinetic energy in the first example does not depend on $k$. Thus we can infer that the kinetic energy depends on neither $g$ nor $k$. That is:
$$E_i(m,v)=E_f(m,k,x)$$ 
We can use dimensional analysis as we did earlier to figure out the proper exponents.
$$\beta m^av^b=\gamma m^ck^dx^e$$
$$M^a \left( \frac{L}{T} \right)^b = M^c \left( \frac{M}{T^2} \right)^d L^e$$
$$M^aL^bT^{-b}=M^{c+d}L^eT^{-2d}$$
$$a=c+d$$
$$b=e$$
$$-b=-2d$$
Let $c=v$ and $d=u$,
$a=v+u$
$b=2u$
$c=v$
$d=u$
$e=2u$
So we have:$$m^{v+u}v^{2u}=m^vk^ux^{2u}$$
Let $u=1$, $v=1$
$$m^2v^2=mkx^2$$
$$mv^2=kx^2$$
For other values of $u$ and $v$ we get the same equation. Notice how the mass must always exist on at least one side of the equation.  
At this point, we know that the kinetic energy depends on the speed of an object, and may or may not depend on the mass. The potential energy depends on the height above the ground, the acceleration due to gravity, and may or may not depend on the mass. The spring potential energy depends on the spring constant and the amount compressed, and may or may not depend on the mass. 
So if potential energy does not depend on mass, we have:
$E_{potential}= \alpha gh$
$E_{kinetic}=\beta v^2$
$E_{spring potential}=\gamma \frac{kx^2}{m}$
If potential energy depends on the first power of mass, we have:
$E_{potential}= \alpha mgh$
$E_{kinetic}=\beta mv^2$
$E_{spring potential}=\gamma kx^2$
If potential energy depends on the second power of mass, we have:
$E_{potential}= \alpha m^2gh$
$E_{kinetic}=\beta m^2v^2$
$E_{spring potential}=\gamma mkx^2$
We use the one where the potential energy depends on the first power of mass, but it seems to me as though based on this preliminary analysis, that any of these 3 sets of equations may be defined as the 'energy'. 
Of course, we haven't considered the fact that the spring potential energy does not depend at all on the mass of the object compressing it. This would restrict our formulation of the potential, kinetic, and spring potential energies to the second version above. Also, we haven't figured out the values of the constants of proportionality, $\alpha$, $\beta$, and $\gamma$. The best I could do was find the ratio of $\alpha$ to $\beta$, which is 2:1, using kinematics. Still, I think we've gone pretty far, considering that we've only needed to use some intuition and a little algebra ;)
A: This is a nice question, but I think it needs to be refined quite a bit. From the given information, the conserved quantity we end up with could be mass, energy, angular momentum, or electric charge. Also, the result for something like energy can't be uniquely defined based on the given information, since, e.g., a relativistic expression would also be consistent with all the given information. Or we could have $E=bE_o$, where $E$ is the quantity we end up defining, $b$ is a constant, and $E_o$ is the quantity defined in textbooks. Based on these examples, we clearly need some more postulates, maybe something like the following:


*

*The conserved quantity has to be additive and has to describe the state of the system (necessary for any conservation law).

*The domain of applicability is mechanics (otherwise we could be talking about conservation of charge).

*No new unitful constants will appear (or else we could have possibilities like the relativistic expressions, which contain $c$).

*Energy is a scalar.

*Conservation of energy is equally valid in all inertial frames.

*There is a gravitational field $\textbf{g}$, which is static and uniform and gives the acceleration of free-falling objects.

*Time-reversal symmetry holds.
From assumption #2, we expect these expressions to involve $m$ and $\textbf{v}$. From assumption #6, the expressions should involve $\textbf{g}$ and the position vector $\textbf{r}$, and from #5 the choice of an origin of coordinates for defining $\textbf{r}$ must be arbitrary. By #1, the only powers of $m$ that can appear in any term are 0 or 1. By #1, things like the acceleration vector can't appear, since they don't describe the state of a system (e.g., you can impose an initial position and velocity on a baseball, but it doesn't "remember" its initial acceleration).
The easiest scalars to form from these ingredients are 1, $m$, $m\textbf{v}\cdot\textbf{v}$, $m\textbf{g}\cdot\textbf{g}$, and $m\textbf{r}\cdot\textbf{r}$. The constant 1 is uninteresting because it doesn't affect the predictions of the conservation law. If mass is a fixed property of our particles, then the same applies to $mg^2$. We can't have  $mr^2$, or any expression involving $r^2$, without violating 5, since the choice of origin for $\textbf{r}$ is arbitrary. The only winner so far is $mv^2$, and this makes us suspect that energy should be unchanged under time-reversal (not odd under time-reversal, which would also be consistent with #7).
With mixed dot products we can get $m\textbf{v}\cdot\textbf{g}$, $m\textbf{g}\cdot\textbf{r}$, and $m\textbf{r}\cdot\textbf{v}$. By #7, energy can't involve addition of terms that change under time-reversal and terms that don't. Therefore $m\textbf{g}\cdot\textbf{r}$ is the only one of these that is going to be OK. This has the same units as $mv^2$, which is consistent with #3.
Putting together the two terms that look interesting so far, we have something of the form $\alpha mv^2+\beta m\textbf{g}\cdot\textbf{r}$. By #6, we need $\alpha/\beta=-1/2$. For consistency with arbitrary historical convention, let's take $\alpha=1/2$ and $\beta=-1$.
Having come this far, we can already do a ton of physics. We can successfully predict the motion of projectiles and the behavior of particles in elastic collisions. By transforming from one frame to another (#5) and requiring collisions to conserve energy in both frames, we can prove conservation of momentum.
We could also build up other scalars through scalar triple products, but to keep them from vanishing identically they'd need to be of the form $\textbf{v}\cdot(\textbf{g}\times\textbf{r})$ (or similar expressions in which these three variables are permuted, but those are identical to this one up to a sign). But this is odd under time-reversal, so it doesn't work.
Examples like $m(\textbf{v}\cdot\textbf{v})(\textbf{v}\cdot\textbf{v})$ violate #3.
