Ninjas scaling walls - Heights in 2D?

Check the image below:
http://www.bgdf.com/node/3559

If you are an illustrator, tell me if it's doable. I think it could be.

Keep thinking!

I had the same game design idea.

My solution was to use a square hex map where 1 hex = the maximum vison range of a unit. Or units can see at most in adjavent hex.

Each hex will contains various features like houses and bushes. The location of the player pawn will indicate where is his. Ex: on bushes = hidden in bushes.

It is very hard to implement this theme and it will take me a lot of time before I figure out.

One thing for sure is that you want either to go with a very high level abstract point of vie, or a not so detailed level. because for example, you cannot design an AI to make units move on the board and plan ambush points.

This is why I thought of using larger hex. A ennemy in the hex means that there is an ennemy nearby and my location will influence his detection success. Then everything is a matter of stats or roll to know if you neutralise your ennemy.

I'm with Reefknot's idea. Having a video-style "from the side"-view can be illustrated very nicely. This will make it easy to see whether a player is located on the roof, inside the building or in the dungeon blow ground.
Some ideas:
1) have secret passages such as ventilation shafts and sewers that are shortcuts that only can be used by ninjas, but not by other characters. Maybe some of the enemy characters can move through some of these (guard dogs can run through a small opening, but cannot climb walls, guard alligators can only move in the sewers etc.). Some of these passages makes moving very fast (don't use hexes but rather differently sized zones depending on how fast you move in that specific location).
2) at some locations, it is possible to see from the roof-level down to the floor below (windows or doors) which opens up for assassinations from above.
3) use cardboard markers that can be flipped for the characters. This can show whether the character is on alert or not.
4) the ninja cardboard markers can also be used for secret moves. Say that a ninja uses a smoke-bomb. He changes his ninja-cardboard marker to 3 hidden markers stacked on top of each other. 2 of this markers are blank on the hidden side, while one of the markers has a ninja on it. Only the player who threw the smoke-bomb knows which is the true on. During the smoke-ninjas turn, he moves all three markers in different directions. The other players do not know which one is the real ninja and which ones are fake. These markers are revealed if someone gets close enough to see the presumed ninja. Then flip it and see if it was the real one or a fake.
5) to make the world a little bit more 3D, you can use multiple "from the side"-view. What I mean is if you have your first "from the side view" in front of you going from left to right, you can have another "from the side view" below it. At certain points in each "from the side"-view it is possible to move from one "from the side"-view to the next. Maybe the first row is the castle, the one below the castle is the village and the one below it is the forest.
6) At certain locations, the ninja can buy/get stuff in the form of different cards. In the forest, the ninja might find the old grand-master ninja that gives him access to the "special ninja killing blow"-card, in the village the ninja might buy a "ninjato made by the mastersmith" or get a mission at the local tavern.
7) have the different enemy characters move in some simple random fashion. Roll a dice: 1-2 on alert, 3 move left, 4 move right, 5 rest, 6 roll twice

...ok, maybe I should stop writing now...
Good luck!

I like the idea of each room sectioned into different levels. To get an interesting perspective on you might do this graphically, check the old school CLUE boards - the rooms in the corners with secret passages had an elegant design.

Still have a problem with ceilings

You can assume stuff. For example, you can assume that if a player has the right skill, when an enemy enter a room, it will automatically try to hide himself and if he can climb on ceiling, he will do so. So climbing to ceiling would only mean better concealment success. You don't need to keep track that he is on the ceiling. But inside or or the roof of a house might be a good idea to mark it since you cannot switch that easily.

Advanced Squad Leader does this with cardboard counters, and it works. There are a number of markers like "Level 1", "Level 2", "Rooftop", ... plus also special markers for units currently climbing at different levels (a cliff or the outside of a building for instance), for being in sewers or a cellar below a hex and probably a few more I forgot. Just stack all the units in a hex with markers inserted to separate the parts of the stack that are at different levels (no markers required as long as everyone are on the ground level). A unit is on the level of the first such marker you find below it in the stack. Other tactical wargames do the same thing, but I think ASL is the closest match since it also handles climbing etc (not allowing units to hang from ceilings though :) ).

The game you describe is in essence a tactical man-to-man wargame. Some of those that focus on combat in built-up areas are bound to also come with detailed rules on how to handle units on different levels within the same area, or units in the same area but in different cover. Before reinventing too many wheels that is probably a good place to look for inspiration.