If you can't localize, you can't do anything that requires localizing.
If you can't use wheel encoders accurately enough to do a rectangular fill (parallel lines) then, by the same reasoning, you can't use them to do any other shaped fill pattern either (concentric circles, spirals, etc.).
I only see one real solution here (that's not random walk), but its success depends on the physical construction of your vehicle and the sensors you're using.
Use the pressure sensor to indicate depth, then build a PID controller around the pressure sensor to steer the vehicle. Your x/y coordinates of the "rectangular" path you're trying to traverse aren't actually x/y coordinates. You're in a cylinder; they're cylindrical coordinates. Really you have h/$\theta$ coordinates.
You're still left with the problem that you can't localize, so you have no absolute $\theta$ coordinate, so you'll never be able to guarantee any coverage in a particular $\theta$ range.
What I would suggest you consider instead of rectangular regions, if you're attempting to make a "cleaning crew" that will work cooperatively to clean the whole structure, is to use cylindrical regions.
So, let's say you have four robots. You could have each robot clean the entire height (0 to h) and a quarter of the circumference (0 to $\pi$/2, etc.). But you can't do this, because there are (presumably) no features by which you could localize in the tank. Every $d\theta$ looks like every other $d\theta$, so you can't assign any robot a particular range in the $\theta$ dimension.
What I'm suggesting you do instead is to have each robot clean the entire circumference (0 to 2$\pi$), then segment by height. Each robot has a pressure sensor and can tell that they are in their correct height band.
Now all you need to do is know that your wheel encoders are accurate enough to detect that you've traversed the circumference plus some overlap tolerance.
This solution requires your ability to resolve your depth accurately. How accurate? I would say you should be at least half the width of the cleaning instrument. If your brush is a foot wide, then you should be able to determine depth accurate to +/- 6 inches. This ensures you're still cleaning in the desired band if you go off-target. This is the minimum resolution; ideally you'll get something much better.
You'll probably want to overlap by (brushWidth - depthAccuracy) to ensure complete coverage where you went off-track during a normal sweep. So, again, if your band is (brushWidth = 1 foot), and you go off-track by -0.5 feet, then the upper +0.5 foot of the band was not cleaned in that segment. Therefore you'd want to overlap (1 foot - 0.5 foot) = 0.5 feet to ensure the whole band was cleaned.
So, your algorithm flow would look something like:
desiredHeight = 0;
finishHeight = h/4;
brushWidth = 1; % Foot
depthAccuracy = 0.5 % Feet
speed = 1; % Percent
circumferenceOverlap = 1.1;
while (desiredHeight <= finishHeight)
while (deadReckoning < circumference*circumferenceOverlap)
actualHeight = PressureSensor();
steerDifferential = PID(desiredHeight-actualHeight);
LeftWheel.Speed(speed - steerDifferential);
RightWheel.Speed(speed + steerDifferential);
deadReckoning = deadReckoning + (LeftWheel.Distance() + RightWheel.Distance())/2;
deadReckoning = 0;
desiredHeight = desiredHeight + brushWidth - depthAccuracy;
So, briefly again, just keep a running count of how far you've traveled with the wheel encoders. Once you've gone a full circumference plus some tolerance, then increment the height and clean another circumference. This solution leverages the fact that the tank is a cylinder, and that (start = end) on the $\theta$ dimension.
Now, if there are sparse obstacles that maybe you couldn't use to localize everywhere (couldn't see for example), you can setup an avoidance subroutine to go around it. But this should clean the entire tank efficiently. You'll want to tune the PID controller to keep the vehicle on track, but that performance will again be determined by the resolution on the depth sensor.
A word of caution: the pressure sensor corresponds to a depth, as in below the water line, not a height. You should be able to detect the surface of the water by an ultrasound reflection at the air/water interface, and likewise should be able to detect the bottom of the tank by the reflection at the water/tank interface. You should take this into account if you're planning on cleaning the entire tank and not just the submerged portion of the tank.
Also, any flow in the tank will affect pressure readings, which will cause false depth measurements.