If solar were free, but we still needed to pay for battery storage, how would it then compare in cost to fuel-based alternatives (fossil fuel, nuclear etc)?
It's relatively high, the problem is that building new dams is an environmental disaster, and existing dams are two orders of magnitude below needed capacity.
Also, hydro dams kill a lot of people when they have accidents.
Do you have to dam a river to store energy in this way? Can they just build water towers that pull water from underground up into a tank and release it via gravity to generate power when needed?
Not enough energy. Hydropower reservoirs are typically many square kilometers of water surface, depth > 10 meters on average and a height differential on the order of 100 meters or more. Vary parameters according to geography, but it's not something that can be built without using geology for support.
Obvious solution that I'm sure has already been considered: dig down 1000 meters and build the "below" reservoir there. Even if the "above" reservoir is at ground level, you'll still get 10x the storage.
The water needs to go somewhere to generate power. Most water tables are much closer to the surface than 1000 meters. Meaning, the water would have no way to go without pumping it back up...
That is where the storage presumably comes from, you use the excess energy to pump water out of the hole. I think the whole thing would be just as geology dependant as the conventional arrangement but with the added expense of digging down 1000m.