I do a lot of work in GPS and thus far there isn't anything reliable.  I'd be interested in helping (as a GPS expert and scuba diver.)

It depends on your application. Using RF frequency to estimate location would not be practical in depth higher than a couple of meters.

You could perhaps replicate the scheme of satellites, just place some "beacons" on the surface and then use high frequency sound waves as a substitute for RF in GPS. You can even use the GPS to dynamically determine the location of the beacons.

Theoretically, if your detector is good enough, you can use ~10kHz to avieve accuracy of ~1m...

Theoretically it's impossible to use gps underwater, because of the simple reason that the RF signals can't propagate underwater and especially the salt water. 

So, to do that, we need to use ultra low frequency bands or acoustic waves which can propagate in water. 

For my point of view, a GPS for underwater might be a hybrid of ultra low frequency and RF systems that can be floating on the surface of sea, using of example some beacons 

Of course we could replicate what we did with RF underwater using acoustics.  It would be massively expensive though, so we'd need a good reason for doing it.

Although acoustics propagate through water with much less attenuation than RF signals, the issue of propagation velocity of acoustic signals through sea water is very important. GPS geolocation compares relative timing of signals from satellites at known locations, with the implicit understanding the these signals all undergo almost identical propagation velocity. Even if there were many sonolites in the ocean at precisely known locations, the variability of acoustic propagation velocity in the ocean would make position reckoning by that method much less accurate.

GPS requires 4 to 9 satellites to be in view to make accurate timing measurements and thus location measurements.  Pure GPS underwater is therefore not possible however I took this question to mean, "How can you enable underwater location services".  This would be possible by the installation of underwater beacons that emit low frequency signals which may be used to enable timing measurements. 

Low frequency signal can travel a great distance underwater.  You can do underwater measurement with an electrical signal from a transmitter is converted into a sound wave by an underwater transducer, called a hydrophone. When the wave strikes something such as a the bottom (or a fish) it reflects back and the timing will indicate distance.  This technology is commonly used as "Fish Finders".  

If beacons can be placed strategically on an ocean floor a simple receiver maybe able to act as a "GPS".  

Look at a very simple example.  Imagine a beacon located at the 18th parallel that is transmitting the current time.  If I am swimming and trying to locate myself, my under water GPS may show that at 12:00:01 PM I receive a signal for the beacon that states the beacon transmitted it's time signal at 12:00:00 PM.  Therefore it took the signal took 1 second to reach me.  I now know that I am 1,500 meter from the beacon.  (Sound through seawater travels at 1,500 meters per second.).  This gives me my possible location as a circle.  A second beacon and third beacon will pinpoint my location at the floor of the ocean.  

The speed of signals vary based on water temperature and pressure but if the GPS device and the beacons are at the same depth, this should enable correction of the distances measured.

A signal beacon my be useful to navigating a diver to a specific attraction or getting them back to the dive boat or shoreline. 

Would it be possible to have some kind of accelerometer (or a liquid inside a sphere with an array of sensors all around the surface) to start working whenever we go under water and start registering relative movements? So, when we are on the surface of the water, we are registering absolute position with GPS, but as we get under water the accelerometer takes place and starts registering relative movements. Whenever we surface again the relative movements can be scaled/corrected with the aid of the absolute position given by GPS.

This would not allow for real-time positioning but would allow for trajectory tracking.

First off, sound (or that frequency) travels extremely well underwater. I can see an array of sensor spread evenly across and area of water and pointed into the water that transmit different frequencies. As you pass under each, your on board "GPS" device detects the specific frequency and can display your current location because it has a map of the sensors locations by frequency.

Since the map could be cumbersome to maintain because you have to know the location of each sensor floating above you. A more complex systems would be free floating devices with GPS in each that simply transmit their lat/long into the water and you receive it as you pass under it. The precision of your map would be based on the number of floating GPS transmitters, their distribution and the diameter of the cone signal they transmit.

A true Rube Goldberg

See ArtemisPRO. This provides GPS positions and other functions like multi-beam sonar, photo, etc. Cheaper variants exist as well.

The most similar to GPS underwater are underwater acoustic LBL navigation systems, particularly those with floating base points, particularly with transmitting base points (like in real GNSS systems). In that case the position data calculates in a submerged acoustic receiver, it can be unlimited number of such receivers estimating own position simultaneously (once again, like in real GNSS systems). We manufacture such a system which is I believe the most similar to real GNSS-systems from users point of view (with receivers for divers and integrated version for ROVs/AUVs, you can google DiveNET GPS or RedWAVE GPS) it emulates GPS-receiver’s protocol and provides geographic position with 1m accuracy in area 700x700 m with four floating retranslators. The point is in the letter “G” - to be a Global Positioning System the entire water surface on the earth should be covered with acoustic retranslators, which is quite impossible, at least for now. Sometimes it can be a misunderstanding in terms: people call any underwater navigation (an underwater object estimates its own position) or tracking (the position of an underwater object is estimated by someone from the surface etc.) an “underwater GPS”. So, any underwater GPS should be at least a navigation system.

Hope it helps!