I don't really understand why that isn't already perfect, at a glance I can tell the depth.
If it gets darker+darker as it gets deeper, eventually it will be black, most people understand that black means it's so deep that no light gets down there.

Reading this made think, if you really wanted to add so many layers. What you could essentially do is have different world maps all linked together. For example in reference to that image in which the tiles get darker as the area gets deeper, it could then eventually just be pitch black. A player could then jump through that to realize the player is now on just a lower layer. Its pitch dark so they would need some lighting.

ex.
tile layer 1 _ _ _ _ _ _ _ _ _ _
tile layer 2 _ _ _ _ _ _ _ _ _ _ _ _
tile layer 4 _ _ _ _ _ _ _ _ _ _ _ _ _
tile layer 5 _ _ _ _ _ _ _ _ _ _ _ _ _ _

so on that little representation there, layer 5 from a top down view would be pitch dark and could potentially be just a endless void. This is all part of game map. When the player goes through layer 5 and jumps through that little entrance there.

player lands on new game map

tile layer 5 _ _ _ _ _ _ _ _ _ _ _ _ _ _
tile layer 6 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
tile layer 7 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
tile layer 8 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

with such a method, you could potentially have plenty of layers, you would essentially have players just jumping through different game maps. If done right, getting layers pre-loaded and what not, it could be sync seamlessly with as much depth as you need.

Or use blender to model, texture and render the look you want if you're frustrated with figuring out which 2D styles to apply to make it appear 3D ;D

I don't know if the camera is stationary, but if it isn't, you could do some subtle parallax scrolling to add to the effect. Although I'm pretty sure it won't be enough to bring out the depth, you'd need something else to go with it.

I would start by narrowing the scope.

Narrow it to only having 5 "navigatable" layers in any image. Meaning what you actually put on the screen, the actually map can have some 500 layers but withing the view area there will only be 5 layers players will move around on. This means that you're accepting something along the lines of say being able to only move up and down 10-20 feet for every 100 or so feet(the area you can see).

For areas that are more than 5 layers deeper than where you are I would make that background move "slower" than the foreground based on how far away it is. When I 've done this in a 2D platformer it was just a simple division for moving the background at a different speed(you can see this same effect in a lot of 2D platformers). This game(Fortune Summones) notable for having 3 to 4 layers at time

For areas that are more than 5 layers above the player I would probably make the area not visable, and make the area that would be "blacked out" and show the cliff face. Not sure how to make it exactly compatible with the previous method and still look good.

If I were you I would ask myself a question - does top-down perspective really fit the gameplay style I want to achieve? If your players are going to spend lots of time building things and navigating three-dimensional space, they might find top-down perspective frustrating, if not unplayable. I'd consider isometric view + transparency and/or screen rotation for better navigation. Measuring depth and building would become very simple that way, but you might also need to get better quality / more detailed graphics for that.

Realistically a method that indicates depth per tile can't represent infinite depths, as there's a limit to the colours, blur level, etc available.

Gotta agree with this one. Even technically speaking, with heights measured in Integers or Longs, there are limits to how far you can go. If you're looking to change the brightness of the blocks based on depth, you could logically only go as high as your variables let you. However, in terms of having unique brightnesses for every depth, there is only a limit of 256 depths available using the RGB or hex spectrum (not entirely sure about HSB or CMYK, but pretty much the same idea).
Alternatively you could have an overlaid square for each tile. If the tile's depth is above the normal height, the tile's color would be white, starting transparent and becoming more and more opaque as depth increases. If it's below, the color would be black.
Either way, there are limits on the technical side to be considered, and they would have to be proportionally done.

Another way to show depth which hasn't been mentioned is also particle effects, that can only exist in or below certain depths. For instance, on really low depths you could have faint mist clouds. If you are on a cliff above a dark pit, the clouds could make you feel that you're high up.

As for your navigation between depths question, you have plenty of methods you could do depending on the setting:

• If there are structures built, you could have doors, teleporters, or portals to bring you to really different levels.
  
• You could also include slope blocks or stairs, which could have a gradient from one layer color to the next.
  
• Of course, players should be able to fall down from higher levels.
  
• etc.