How should the VFR Cruising Altitudes (FAR 91.159) be applied over rising terrain?
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.