The cube exerts a force equal to its weight on the water below it,
This is incorrect, and leads to many other errors in your thinking.
The force on a submerged object in a gravitational field is easily calculated by considering the pressure in the fluid at each vertical position. That being the case, all the horizontal forces add to zero leaving only the forces on the top and the bottom which are different.
Now lets consider a submerged cube oriented with vertical and horizontal faces. The downward force on top ($\rho_w g d_{\mathrm{top}}A$) is less than the upward force on the bottom ($\rho_w g d_{\mathrm{bottom}}A$), where $A$ is the area of the face of the cube, $\rho_w$ is the density of water, and the $d$s are the depths. There is also the weight force on the cube which is totally independent of the liquid, so there are 3 important forces.
Now, the sinking or floating of the cube depends on the density of the cube. Summing the forces, taking down as positive, we have
$$F_{\mathrm{down}}=\rho_w g d_{\mathrm{top}}A-\rho_w g d_{\mathrm{bottom}}A +(\rho_{\mathrm{cube}}Vg).$$
Now the length of one side is $A^{1/2}$, so the volume is $A^{3/2}$ and $d_{\mathrm{bottom}}-d_{\mathrm{top}}=A^{1/2}.$ Substituting gives us
$$F_{\mathrm{down}}=\rho_{\mathrm{cube}}gA^{3/2}-\rho_wgA^{3/2}=gA^{3/2}(\rho_{\mathrm{cube}}-\rho_w).$$
So, if the density of the cube is greater than the density of water, there is a net downward force. If it's less, there is a net upward force.
Imagine that the air in the atmosphere was just somehow sitting there unpressurised. What would happen?
Well, Earth's gravity would be attracting all that air towards the centre. So the air would start to fall downwards.
The very bottom layer of air would be prevented from falling through the solid surface, as the air molecules rebound off the molecules of the surface. But the layer above that doesn't stop. So Earth's gravity forces the air in the lower part of the atmosphere to accumulate against the surface of the planet, becoming more and more dense.
As the air gets denser near the surface, it becomes more and more likely that air molecules collide. That's what air pressure is: the average force of all those air that would hit a surface you placed in the air. But the air pressure also acts on the air itself. So eventually the force of the air pressure at the bottom layer of air pushes up on the layer of air just above it enough to counteract the pull of Earth's gravity on that layer of air. And so you get another layer that is prevented from falling.
But the air above that is still being pulled down, and so more air is being squashed down into this second layer above the surface. This increases the force that the bottom layer needs to provide to the next layer; the air molecule collisions not only need to provide enough force to counteract the weight of the air immediately above it, but also to provide those molecules with enough momentum that when they in turn collide with the air in the third-bottom layer it can support the weight of that layer as well. So more air squeezes down to the surface until the pressure at the bottom layer is sufficient to support the weight of the 2 layers above that.
Obviously the atmosphere isn't actually split into discrete layers like this1, but hopefully it's a helpful way to think about it. You should be able to see how gravity squeezes the air down against the solid surface, until the pressure at the bottom is just enough to support the weight of all the air above it.
This is why air pressure drops off at higher altitude. As you go up, there is less air above squeezing down, so equilibrium with gravity is reached at a lower pressure.
So it's not literally that the air pressure you feel is the weight of the column of air above you. It's not that your head is somehow "holding up" a 100km column of air above it. But the air pressure of the air surrounding you must provide an equivalent force to the weight of all the air above it. If it did not then the weight of the air above would be partially unsupported, so gravity would squeeze it down further, increasing the pressure until it was equal to the weight of all of the air above.
This is also why the top of your head doesn't feel any difference in air pressure to the side of your body. Air pressure is the same in all directions, because the air molecules are really just zipping around in countless different directions, uncoordinated with each other. Those molecules colliding with things must supply enough average force in the upward direction to support the weight of the atmosphere, but when the pressure increases due to gravity it can't cause a coordinated force that is only upwards, so there is just as much force from air pressure on the side of your body as there is on your head.
1 And if you actually had the atmosphere of Earth spread out in a diffuse low pressure cloud and let it all fall under gravity the results would be much more exciting than I have described.
Best Answer
I would assume it is was part of evolution that we don really feel it, because it would be very annoying to be continuously aware of the normal force.
However, you can try several things to redistribute the normal force, such that you start to feel it.