If going full 3d just for the walls is too much, I'd suggest 'hard coding' the 3d just for the walls.
One way of doing this, if you can create and change shapes in runtime: every wall is a 2d square. 4 vertices, vertex1_bottom, vertex2_bottom, vertex1_top and vertex2_top. Make bottom vertices move with the foreground and the other two vertices would be slightly displaced and move with a slightly larger velocity. This is the usual technique for parallax effect in older games (8/16 bit, for example) for the background, only here you would be using it in a different way.
The equations for the displacement and velocities are actually quite simple. If we put the coordinate system on the center of the screen (this is very important) all you have to do is scale the top vertices according to the bottom ones:
v1_top = factor * v1_bottom;
v2_top = factor * v2_bottom;
You might need to experiment with the factor. Basically, the higher this factor the closer to the camera the top of the walls will appear (a low value will probably work best).
I'm making this stuff as I write so there may be some conceptual problems. Let me know if you find any. Hope this helps :)