Why does it make any physical sense for a body to have negative potential energy? Sorry to ask the long way, but trying to make the question clear so that I can get a clear answer. 
Why does it make any physical sense for a body to have negative potential energy? 
If a body A is at infinite distance from another body B, it has zero gravitational potential energy, but if it is at "zero" distance from another body B, it has negative infinite potential energy, and acquires infinite kinetic energy in the process of getting there.
Please don't tell me that the zero point of potential energy is arbitrary, and it could just as well have zero potential energy when it is at zero distance from another body B, and positive infinite potential energy when it is at infinite distance from the other body B. How can it have this? When body A is at infinite distance from the other body B, then it is not influenced by the other body B at all, it is as if the other body B does not exist at all, so then the potential energy in body A must be zero, as there is no gravitational field of the other body B to cause any potential energy in body A.
But then the question is if the potential energy contained in the body A is zero at infinite distance from the other body B, then how is it possible for this zero potential energy to be reduced further and get changed to kinetic energy as the body A accelerates towards the other body B, so that the potential energy becomes negative? As I see it, if the body A never had any potential energy to begin with, then this not present energy cannot change into kinetic energy, otherwise we would be creating kinetic energy out of nothing. 
Why does it make any physical sense to say that the body is in "potential energy debt", ie the potential energy is reduced to negative when it was zero to begin with?
 A: *

*Imagine a ball on a shelf. There is some potential energy stored.

*Now it falls to the floor. The potential energy becomes zero.

*Now there is a hole in the floor. The ball rolls down there. This reduces the potential energy. Because we know that potential energy reduces with height (with distance between the objects).


So what value does the potential energy have now? Is it negative? Yes it is. What does that mean? Nothing. It only means that the ball will rather want to be in this hole than at the floor. In the same way that it rather wants to be at the floor than on the shelf.
The value of potential energy is irrelevant. Only the difference is important. Because objects always want to move towards a situation of lower potential energy. Asking how the potential energy can be $-10 \;\mathrm J$ is thus no different than asking how it can have the value $10\;\mathrm J$. The scale just happens to be in the negative range in the first case. And that is irrelevant and not important.
A: It seems you are excluding conservation of energy considerations from your question.  Given the total energy is conserved, that energy can be converted between potential and kinetic, that the potential energy is $0$ at infinity, and that the masses would gain kinetic energy through their mutual attraction, it follows that this gain in kinetic energy - a quantity that is classically non-negative - must be at the expense of the potential energy.  Thus the potential energy may be in debt but the kinetic energy is not, and the total energy remains constant.
A: There's a few things here.  First off, your approach of having the potential be zero when the distance between the object is zero, and infinite as it approaches infinite distance has a flat: this would make the potential energy of any two objects at any finite distance infinite.  That's a side effect of the gravitational potential energy having a $\frac{1}{r}$ term in it.  This really gives us permission to use any point other than r=0 as a reference point.
In the astronomical world, there's not always an obvious place to put this reference point.  When it comes to activities on the Earth, we often put the reference point at the ground, but that reference is terribly Earth-centric.  For astronomical work, that's not convenient.
So the interesting question is why we put the reference point on the ground for Earth based activities.  After all, the first gravitational potential energy equation we learn is $E=mgh$.  The trick is to choose a convenient point.  If we choose the reference point of "on the ground," for the most part the PE=0 reference point has useful physical meaning.  If we want to convert any more of the gravitational potential energy into kinetic energy, we need to dig a hole.  For most of our actions, that isn't an option, so this manes that PE=0 line really convenient.  A lot of extra terms in the equations cancel out by doing so.
When it comes to astronomy, we're far less interested in things hitting the surface of Earth (and when they do, they tend to dig their own holes!).  The surface of the Earth is no longer a convenient reference point.  So we choose, instead, to put it at $r=\infty$.  Why?  Because it's the one reference point that every object in the system can agree with.  When you're at distance $\infty$ to one object, you're at a distance of $\infty$ to every object, and that proves to be a really convenient reference point.
The side effect is that all potential energies here are negative, as you noticed.  This is quirky, for sure, but for general astronomical uses, it's an acceptable quirk.  It just means astronomers don't get to assume that an object runs out of potential energy at PE=0.  They have to have other constraints, like $PE=-\frac{GM_{Earth}m}{r_{Earth}}$, which is the potential energy of an object when it strikes the surface of the earth (a negative number, of course).
The numbers are just tools in a model.  It is up to us to understand how they should work and what they should mean.  For astronomers, it was convenient to treat PE as a negative number, referenced from $r=\infty$.  An aeronautical engineer is far more likely to reference it from $r=r_{Earth}$, because airplanes stop working well when their altitude is 0.  Use whichever is convenient for you, but do realize that the vast majority of scientists agree on where the reference points should be put, within their particular discipline, and they have likely chosen them to be the most convenient places.
A: 
If a body A is at infinite distance from another body B, it has zero gravitational potential energy, but if it is at "zero" distance from another body B, it has negative infinite potential energy, and acquires infinite kinetic energy in the process of getting there.

It's not a good idea to bring in the infinities which arise when modeling objects as classical points.  It's well known and understood that things like point charges and point masses are extremely useful tools in classical physics, but lead immediately to nonphysical infinities if you ask the wrong questions about them.  If you want to be safe, then replace your point masses with little grains of sand or dust or something, so your statement becomes "if it is touching another body B, it has negative potential energy $-U$, and acquires kinetic energy $U$ in the process of getting there."

Please don't tell me that the zero point of potential energy is arbitrary, and it could just as well have zero potential energy when it is at zero distance from another body B, and positive infinite potential energy when it is at infinite distance from the other body B.

Nobody says this.  It's true that the zero point of potential energy is arbitrary, but the gravitational potential function for a point mass is singular at $r=0$, so that's the one place where you can't define the gravitational potential to be zero (or anything else - the potential function is undefined here).  If you adopt the "grain" picture I mentioned above, however, you're free to set the zero point wherever you wish, at least in the context of non-relativistic physics.  
You are assigning a bit too much physicality to potential energy, I think.  Potential energy is simply a function of position which is defined in such a way that as long as the associated force is the only one doing work on the body, then the combination $E=KE + PE$ remains constant.  But of course, if I added $17\ J$ to the PE at every point, then that total would still be constant.  The physical thing is the potential energy difference between two points in space, not the actual value of the potential energy at any particular point.
A: Your mistake is in assuming that the value of potential energy is relevant, like when you say that if two bodies don't interact there should be zero potential energy. In fact, what matters is not how much potential energy a body has, but whether it could have less by moving somewhere else. In the standard convention, the gravitational potential between two bodies is negative, and by moving closer this potential energy will be more negative; the energy lost is converted into kinetic energy.
"Bodies being infinitely apart" is not something that can actually happen: it's just an approximation. As the objects move farther and farther away their potential energy increases towards zero, but this is not very important; what matters is that the curve becomes flatter. That is, they would lose less potential energy by moving a fixed distance, so the force is smaller.
A: Potential energy isn't a thing that exists physically. It only makes sense within a context relative to some situation. Saying a rock at the top of the cliff has potential energy just means it will gain kinetic energy if you drop it over the edge. Saying a rock at the bottom of the cliff has negative potential energy just means it will take at least a certain amount of energy to get it up to the top of the cliff (and it's interesting that that's about the same energy (minus friction) you get from dropping the same rock back down). The energy is only meaningful in those contexts. If you talk about rolling those rocks in some other direction to some other place, the potential energy for that would have entirely different values.
A: Why is it weird?
It is observed that in some experiments, e.g., elastic collisions, KE is conserved. However in general,
$$\Delta KE \ne 0$$
In many situations, one new term called PE can be added so that
$$\Delta(KE)+\Delta(PE)=0$$
It is found that the new term is in the form
$$PE(\text{final position})-PE(\text{initial position})$$
In other words, only the difference matters.
This is clear because if KE + PE is conserved, so is KE + (PE + Constant)
The constant can be selected such that the potential energy at some positions are negative.
What is so confusing?
