How should the VFR Cruising Altitudes (FAR 91.159) be applied over rising terrain? Imagine flying at 4500' indicated altitude, 4500' AGL, heading 270, directly towards a steep mountain ridge that tops out at 4000 feet.  Imagine the mountain being almost like a flat wall.

When can I change altitudes to >4500' and still be in compliance with 91.159?  Do I have to wait until I get close to the ridge when I'll be under "3,000 feet above the surface"?  Can I interpret "above the surface" in a more liberal way?


  § 91.159 VFR cruising altitude or flight level.
  
  Except while holding in a holding pattern of 2 minutes or less, or while turning, each person operating an aircraft under VFR in level cruising flight more than 3,000 feet above the surface shall maintain the appropriate altitude or flight level prescribed below, unless otherwise authorized by ATC:
  
  (a) When operating below 18,000 feet MSL and -
  
  (1) On a magnetic course of zero degrees through 179 degrees, any odd thousand foot MSL altitude 500 feet (such as 3,500, 5,500, or 7,500); or
  
  (2) On a magnetic course of 180 degrees through 359 degrees, any even thousand foot MSL altitude 500 feet (such as 4,500, 6,500, or 8,500).
  
  (b) When operating above 18,000 feet MSL, maintain the altitude or flight level assigned by ATC.
First, you said you're cruising at 4500 indicated, but then state that you are 4500 AGL. Indicated altitude is usually MSL, so this means the terrain is at 0 ft MSL until the base of the cliff, which then shoots up to 4000 MSL.

So as you travel westbound at 4500 MSL, you are in compliance with 91.159. The moment that the distance between your aircraft traveling at 4500 MSL and the ground is 3000 feet or less, then 91.159 no longer applies, and you can fly any altitude you need in order to maneuver around or over obstructions at or below 3,000 AGL.

Based on your scenario no action is required, you can just keep cruising along and fly over the cliff at 4500 MSL and 500 AGL over the "flat wall" mountain. 

However, your question would be more interesting (and I'm guessing this is what you meant) if you had said that the flat wall was 5000 ft, because technically if the ground is at sea level up to the flat wall, then you are still more than 3000 AGL up until the moment your aircraft reaches the wall and 91.159 would still apply. The answer to this is that you would have to climb to the next westbound VFR altitude of 6500, and you could do it whenever its needed if you're on your own navigation, or when instructed by ATC if you are on an assigned altitude, or at anytime to avoid crashing into the mythical "flat wall" mountain.

The key is that this rule applies only during "level cruising flight" so when you are climbing or descending 91.159 does not apply, otherwise, VFR aircraft could never get to the upper VFR cruising altitudes.