Terrain height in 2D games

Hello! I'm working on an old-school-inspired game in my free time. It is to be an HTML5 game with all the backend and graphics done by me. I have some decent experience with both sides, so getting a prototype going shouldn't be too difficult. That said, I've run into a bit of a dilemma.

My terrain is all procedurally generated tiles, and I would like to have elevation figure into things. Something simple, like a limited range of 8 possible heights, is what I'm looking for. 

However, I also am trying to keep a very "old-school" style of graphics.

Ideally, I'd like for my game to look and feel similar to an old Zelda or Pokemon title. (3/4 view) But this creates a lot of problems. I can't seem to find a pre-made tileset online that even begins to look correct with terrain height applied. I know that usually this is done the same way as grass region meeting up with a sand region, wherein you have special "edge" tiles. But I can't seem to make that work with more than 2 distinct levels of terrain, plus it would be thousands and thousands of possible transition types (grass meets grass 1 level above, grass meets grass 2 levels above, grass meets sand 1 level above, etc etc etc). This is not to mention the further-along programmatic problems of occlusion and pathfinding and such. (Most of which I would solve by allowing 90 degree rotations of the world)

As a secondary option, I would consider what is commonly called an "isometric" perspective for my game. That has a lot of problems of its own though. I do not like the typical "iso terrain," many games have used. (Example: http://i.stack.imgur.com/rzqj8.jpg) It seems too programmatic in nature. And while the "minecraft-style" of depicting each tile as a block has an appeal, I'd need way more terrain levels and such to provide any fidelity. Also, this style is not my strong suit, drawing wise.


So with all of that in mind, I'm a little stuck. I'd really like to find a middle ground, somewhere between an "Isometric minecraft" and Zelda, where rock walls are basically just a tile type and do not actually indicate height. I'd also really like to keep my 3/4 perspective. Something like this imagehttp://www.fondusis.com/images/dev/FondusisFringe2.png. Though if you know Tiled or any such editor you will realize this is basically a grid of paint-by-numbers, i really need to be able to rotate, and view these hills from the other side. But when I set out to create art for this, it all goes to hell.

Any experiences dealing with art assets of this type, or anything related, will be helpful. Just trying to wrap my head around this problem! Thanks for your time!!