You may want to see Why does kinetic energy increase quadratically, not linearly, with speed? as well, it's quite related.
Mainly the answer to your questions is "it just is". Sort of.
What is a definition of energy that doesn't use this circular logic?
Let's look at Newton's second law: $\vec F=\frac{d\vec p}{dt}$. Multiplying(d0t product) both sides by $d\vec s$, we get $\vec F\cdot d\vec s=\frac{d\vec p}{dt}\cdot d\vec s $
$$\therefore \vec F\cdot d\vec s=\frac{d\vec s}{dt}\cdot d\vec p$$
$$\therefore \vec F\cdot d\vec s=m\vec v\cdot d\vec v$$
$$\therefore \int \vec F\cdot d\vec s=\int m\vec v\cdot d\vec v$$
$$\therefore \int\vec F\cdot d\vec s=\frac12 mv^2 +C$$
This is where you define the left hand side as work, and the right hand side (sans the C) as kinetic energy. So the logic seems circular, but the truth of it is that the two are defined simultaneously.
How is kinetic energy different from momentum?
It's just a different conserved quantity, that's all. Momentum is conserved as long as there are no external forces, kinetic energy is conserves as long as there is no work being done.
Generally it's better to look at these two as mathematical tools, and not attach them too much to our notion of motion to prevent such confusions.
Why does energy change according to $Fd$ and not $Ft$?
See answer to first question. "It just happens to be", is one way of looking at it.
Sometimes when you're stuck on things, it's helpful to look at the mathematics of what's being asserted. For example, nowhere in Newton's three laws does "energy is conserved" appear.
Energy conservation does appear, however, when you have a system that behaves like $m \ddot{x}=-\nabla U$, for some function $U$, where $x$ is a position vector as a function of time. In this case it's a mathematical theorem that $\frac{d}{dt}\left(\frac{1}{2} m \|\dot{x}\|^2+U\right)=0$.
Though it's easy to get carried away and start talking about nature and systems and why some forces can be represented as $\nabla U$, in every regular mechanics book* I've read, this is what things boil down to.
*regular mechanics as opposed to higher mechanics. In higher mechanics one states that the action $A[u]=\int L(u(t),u'(t),t)dt$ tends to be minimized. From that it's a mathematical theorem that if $L(u,\dot{u},t)=L(u,\dot{u},t+t_0)$ for all $t_0$, then energy is conserved. However then your question becomes, "why does nature tend to minimize the action" or equivalently, "why must we use a function like $L$?" To which one must appeal to experiment! There are no proofs of energy conservation just as there are no proofs of Newton's laws!
Best Answer
Something that has a constant velocity[1] has a definite amount of kinetic energy. It would do work if it would exert a net force on something. Let's make a nice and simple model with two objects.
Let's call the first one a baseball. The baseball is flying through the vacuum[2], going it's merry little way. There is no net force on the baseball, and it has a definite amount of kinetic energy.
We have a second object too. A catchers glove. The catchers glove is stationary. It has no kinetic energy.
Right now, nothing is happening, no forces, no work, just a flying ball. But due to an astronomical coincidence, right as we're looking at this situation, the ball is approaching the glove, and hits it! The moment the ball hits the glove, we are in a different situation. The ball is exerting a force on the glove, and the glove on the ball[3]. This means the ball is no longer flying at a constant speed; it's slowing down. the catchers glove starts to move too - it's gaining the amount of kinetic energy that the ball is losing. It is said that the ball is performing
work
and the amount of work it performs is the amount of energy transferred between the ball and the glove.Note however, that the ball started to do work only when it started to exert a force, and thus a force started to work on the ball[3].
So yes, an object with a constant speed/no net force working on it has kinetic energy, which is equivalent to the ability to do work - if it would exert force on something else, in which case it would no longer be true there is no net force working on it. So when it's still flying along at a constant speed, it has the potential to do work. As soon as it starts doing that work, it's no longer flying along at a constant speed.
You could, of course, make things more complicated, and add in a third body that exerts force on the ball equal and opposite to the force the glove exerts on the ball. In that case, there would still be a net force of zero on the ball, and it would not accelerate or slow down, but would still do work on the glove. That changes nothing fundamentally however, and would be equivalent of the third object exerting the force directly on the glove, with the ball taken out of the equation completely. It adds nothing to the understanding of the original question.
[1] or something on which no net force is working - these two statements are equivalent!
[2] yes, we are playing baseball in a vacuum. We're awesome like that.
[3] remember Newtons third law. If something is exerting a force on something else, that other thing is exerting a force on the first thing, equal in size, opposite in direction.