You disabled WiFi and GPS, but you still have cellular data turned on. That means that the phone is in communication with the local cell towers. Android uses cell tower geolocation to estimate your current location.
Each cell tower has a set of ID numbers that identifies them to the phones. It broadcasts its identity constantly so that phones can connect to it as they move around. Cellular tower antennas are directional, with each tower serving roughly three different areas; you can think of them as three pie-shaped wedges with the cell tower at the center of the pie. Each of those wedges is a "cell" (which is where the technology got its name.)
Each of the radios serving those cells transmits using a certain amount of power - the closer you are to the tower, the stronger the signal your phone receives, and vice versa. Your phone uses the received signal strength to save batteries. The farther away a cell tower is, the more power it takes your phone transmit to it. So a cell phone always tries to lock onto the strongest signal so that it can transmit using the least amount of power. A more useful way of looking at it is that received signal strength represents the rough distance to the cell tower.
So now picture that cell, shaped like a wedge of pie, with the strongest signals received closest to the tower, and weakest furthest from the tower. Imagine slicing the wedge of pie in curved lines ringing the tower, with strong signal strength in the closest slice and the weakest signal in the furthest slice. It looks (very) roughly the WiFi logo. Each of those slices represents some tiny area of the planet, and you're standing in one of them.
If you're in a larger populated area, like a city, your phone will usually get signals from more than one cell tower. So picture the intersection of overlapping slices from tower A, tower B, tower C, and tower D. The intersections define a smaller and smaller area.
So how does Google know any of where these cells, wedges, slices, and intersections are? From the billion Android phones that have GPS turned on (including yours, when your GPS was on), constantly sending reports of their GPS location and what cell towers and signal strengths they see. Google has used this data to map out where each cell is located, and what the approximate signal strength is at each point. They have a giant database on their servers with this information; your phone queries that database by making a network request that lists all cell towers that are in range, and the Google servers respond with your estimated location.
It's all very approximate, of course, because radio signals don't actually travel in perfect little pie wedges - they bounce off buildings and cars, they get absorbed by trees and walls and fog and clouds and people. And new cell towers come and go every day, so the radio transmitter landscape is frequently changing, too. The millions of reports produce only average GPS coordinates. But that's OK, because even imperfect location data is still good enough for most user needs.
Finally, for additional accuracy, the Google Play location services software on your phone keeps track of the last known location of your phone, and may use this to better estimate your current location. In particular, the last known location is a plausible estimate for your current location (under the heuristic that you might not have moved since the last time your location was queried); if this seems consistent with cell tower information, it might be used to improve the accuracy of your estimated location.
