What is the origin of gravity? We know that an object that feels no force should travel at a constant speed. But a body accelerating because of gravity feels no force. This seems to be a paradox. Could we possibly find the origins of gravity if we solve this paradox?
 A: This is too broad a question to do it justice here, but basically you are quite correct that the fact a freely falling observer is weightless was the key to constructing general relativity.
The starting point for the work on general relativity was the statement of the equivalence principle. This can be stated in lots of ways, but basically it states that inertial and gravitational mass are equivalent. So when you write Newton's second law:
$$ F = ma $$
and Newton's law of gravity:
$$ F = \frac{GMm}{r^2} $$
The equivalence principle tells us that the $m$ in both equations is the same. The equivalence principle also means that an observer in free fall must experience no force, or technically that their proper acceleration is zero. Trying to construct a theory that includes this principle leads you straight to a class 
of theories called metric theories, and of this type of theory general relativity is the simplest one that works.

Since a stray string theorist has wandered into the hallowed halls of general relativity I'd like to expand on my answer to talk a bit about what is going on. Suppose ACuriousMind is the one falling towards the Earth and I am the one stationary on the surface. And suppose someone has sneaked up behind us and blindfolded us both so we can't see what's happening. How do we know which of us is falling and which is standing on the Earth's surface?

The answer is simply that ACM feels himself to be weightless while I feel my weight i.e. I feel the surface of the Earth pushing me upwards. So even though neither of us can see a thing we both know where we are.
But now suppose someone sneakily removes the earth and places a rocket motor under my feet that accelerates upwards at $9.81$ m/s$^2$. Since there's no Earth there is no gravity so ACM is just happily floating weightless in space. But I feel an acceleration pushing me up just like the Earth's gravity. Both of us are blindfolded remember, so as far we as know nothing has changed and the situation is exactly the same as it was before.

But of course now there is no gravity. Now I am in a non-inertial frame, while you are in an inertial frame, and this is the point made in ACuriousMind's answer. You are accelerating towards me because I am accelerating towards you. So you can be accelerating towards me even though you are weightless.
So why did I jump straight to general relativity? Well let's put the Earth back, and now suppose my brother Albert has dug a deep tunnel right to the centre of the Earth and is hovering there. He is hovering because the gravity at the centre of the Earth because the gravity falls to zero at the centre of the Earth. And since I am stationary on the surface and Albert is stationary at the centre we are stationary with respect to each other. That means ACM is accelerating (as he falls) towards both me and Albert at the same rate.
But, Albert is weightless while I'm not. Unlike before we can't snatch the Earth away and reproduce the situation with rocket motors. For both Albert and ACM to be weightless they cannot be accelerating towards each other.
And this is the key point. We can always reproduce the effect of gravity using Newtonian mechanics and non-inertial frames, but we can only do it locally. That is we can do it for selected pairs of observers but not for all observers. And this is where general relativity comes in.
A: This is not special to gravity, and has nothing to do with the equivalence principle as some comments and answers here imply. 
You are mischaraterizing Newton's laws. We don't know that an object that "feels no force" should travel at constant speed, we know that an object upon which in an inertial frame of reference no force acts should travel at constant speed. And actually, in the non-inertial comoving frame of reference in which the object rests and thus feels no force, we have that the object still doesn't move - but the earth does, so the law still holds - the object feels no force and, in its comoving frame of reference, indeed travels at the constant speed of 0.
Your paradox arises not from anything special about gravity - you could create the exact same "paradox" for any other force between two bodies - but from the failure to distinguish which reference frame we are talking about. In the object's frame, it experiences no force and moves at zero speed. In the earth's frame, it experiences a force and accelerates. 
