IN ANSWER TO THE ORIGINAL QUESTION
Yes, there must be fluid vertically below some part of the object for it to float, but there need not be fluid below all parts of it. The object must have some surface area which has an inward normal with an upward component, so that the water pressure on it has an upward component. For example, the block could float if the sides slope inwards toward the base, as Kieran Moynihan suggests.
In his answer to No buoyancy inside liquid Chester Miller shows that the resultant buoyant force of fluid pressure ("upthrust") on an object which is touching the bottom of a container is $$B=(V-hA)\rho_wg$$ where $V$ is the volume of the submerged part of the object, $h$ is the depth of fluid and $A$ is the area of contact with the bottom of the container.
If the sides of the block are vertical then $hA \ge V$ for all values of $V$. (The equality applies if the object is not fully submerged.) The formula confirms anna v's observation that no amount of water will make the block float, even if it is far less dense than water.
This formula also shows that even if $A$ is very small you can make $B$ negative (ie the "buoyant" force becomes a downward force) by increasing the depth $h$ of fluid. The surprising consequence is that an object which would otherwise float when free of the bottom of the container (ie when there is fluid below all parts of it) can be made to stay on the bottom if a small part of it is already touching the bottom. For example, a large helium balloon can be tethered to the ground using a light suction cup which is much smaller in area than the cross-section of the balloon.
IN ANSWER TO THE QUESTION IN YOUR EDIT
Intuitively you would think that increasing the pressure of the air increases the downward force on the block, making it sink lower in the water, but this is not the case. In both cases what happens to the block does not depend on the pressure of the air but the pressure gradient in the air. If the pressure is uniform throughout the air space, an increase or decrease has no effect on the depth at which the object floats in the water. But if there is a pressure gradient (which necessarily increases downwards) then an increase in the average pressure makes the object rise up in the water, and a decrease makes it sink lower.
Explanation
The explanation is similar to that in Why does a helium filled ballon move forward in a car when the car is accelerating?
The forces on the block are initially balanced. The vertical forces are the weight $W$ of the block and the pressure-forces $F_1$ of the air on the upper face and $F_2$ of the water on the lower face of the block : $$F_2=W+F_1$$ To avoid complications I assume that the block is cuboid so that the areas of upper and lower faces are equal.
Suppose the air pressure is constant throughout the upper part of the container. Then an increase in air pressure increases the forces $F_1, F_2$ equally, so the depth at which the block floats in the water does not change. The increase in pressure at the upper face is transmitted through the air and water to the lower face, increasing it by the same amount.
The air pressure would be approximately constant throughout its volume if the air is only slightly compressible and its density is low compared with that of the water. Both these conditions usually apply at typical atmospheric pressures.
However, if there is a significant pressure gradient in the air then the pressure at the surface of the water will be greater than at the upper face of the block. It is the pressure at the water surface which is transmitted to the lower face of the block, so the increase in force on the lower face would be greater than that on the upper face, and the block would rise up in the water.
Another way of seeing this is to imagine that the air becomes as dense as the water. Then since the block floats in water it will also float upwards into the dense air.
There will be a significant pressure gradient in the air if either it is compressible or its density is comparable with that of the water.