About negative energies: they set no problem:
On this context, only energy differences have significance. Negative energy appears because when you've made the integration, you've set one point where you set your energy to 0. In this case, you have chosen that $PE_1 = 0$ for $r = \infty$. If you've set $PE_1 = 1000$ at $r = \infty$, the energy was positive for some r.
However, the minus sign is important, as it is telling you that the test particle is losing potential energy when moving to $r = 0$, this is true because it is accelerating, causing an increase in $KE$:
let's calculate the $\Delta PE_1$ for a particle moving in direction of $r = 0$: $r_i = 10$ and $r_f = 1$:
$\Delta PE_1 = PE_f - PE_i = Gm(-1 - (-0.1)) = -Gm\times0.9 < 0$
as expected: we lose $PE$ and win $KE$.
Second bullet: yes, you are right. However, it is only true IF they are point particles: has they normally have a definite radius, they collide when $r = r_1 + r_2$, causing an elastic or inelastic collision.
Third bullet: you are right with $PE_2 = mgh$, however, again, you are choosing a given referential: you are assuming $PE_2 = 0$ for $y = 0$, which, on the previous notation, means that you were setting $PE_1 = 0$ for $ r = r_{earth}$.
The most important difference now is that you are saying that an increase in h is moving farther in r (if you are higher, you are farther from the Earth center).
By making the analogy to the previous problem, imagine you want to obtain the $\Delta PE_2$. In this case, you begin at $h_i = 10$ and you want move to $h_f = 1$ (moving in direction to Earth center, like $\Delta PE_1$:
$\Delta PE_2 = PE_{f} - PE_{i} = 1mg - 10mg = -9mg < 0$.
As expected, because we are falling, we are losing $PE$ and winning $KE$, the same result has $PE_1$
Fourth bullet: they both represent the same thing. The difference is that $gh$ is the first term in the Taylor series of the expansion of $PE_1$ near $r = r_{Earth}$. As exercise, try to expand $PE_1(r)$ in a taylor series, and show that the linear term is:
$PE_1 = a + \frac{Gm(r-r_{earth})}{r_{earth}^2}$.
Them numerically calculate $Gm/r_{earth}^2$ (remember that $m=m_{earth}$). If you haven't made this already, I guess you will be surprised.
So, from what I understood, your logic is totally correct, apart from two key points:
energy is defined apart of a constant value.
in the $PE_1$, increase r means decrease $1/r$, which means increase $PE_2 = -Gm/r$. In $PE_2$, increase h means increase $PE_2=mgh$.
To understand your situation, you need to rethink your understanding of the definition of the potential energy.
The best definition for the potential energy is: Potential energy is a measure of work done by a potential force upon the object moving while it is experiencing that force. The change in the potential energy of a body between two positions is equal to work of the potential force upon movement of the body between those two positions.
So, when you specify Potential energy of the body, it is always the energy of a specific [conservative!] force (or a combination of conservative forces), and with respect to some point of reference that you choose as a zero level of that potential energy. (Note that the position is also with respect to the other body that produces the force.)
When you have a single solid body, i.e. there are no external forces acting on it, you do not have any potential energy defined.
So, the answer to your question: in case of a single solid body the potential energy is undefined.
Saying that something that is undefined is zero is not strictly correct.
The case is rather different when the body is not solid, i.e. when its shape is not constant. E.g. if the shape of an elastic body can be changed (e.g. the body can be compressed), - then you have a potential energy related to that deformation.
In that case, you can consider the body as a combination of different parts ("points" of very small mass) of it that are acting on each other with forces. If the object is fully elastic, each of those forces is potential, and then you can associate potential energy with each of them. Accounting for all of them individually is rather difficult, so, an average potential energy for the entire ensemble of these portions (points) is introduced. In this, fully elastic case, this potential energy is a unique function of the shape of the body (i.e. of the relative positions of all the points within that body).
Some other typical examples where the confusion similar to the OP's occurs is the potential energy of a charged particle (e.g. electron) in an electric field. It looks like there is no other "body". In reality, there is a field (electric), which effectively is the representation of another body(ies) acting on this charged particle. Note that in case of gravity, one can define a gravitational field, thus "hiding" the object that creates it.
Best Answer
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."
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.