Good idea, and basically along the lines of my thought as well:
I would plant heat tolerant taller plants such as tomatoes or other plants, maybe even cukes or melons (remember, 3PM means they've been in the sun since around 7 or 8AM) for your location -- i.e. probably not a good idea in South -- next to the cement walls to take advantage and buffer the reflected heat. Pole beans might work too. Then leave enough space between the tomatoes, etc. to plant and harvest the lettuce. This works, too, since you'll be planting lettuce way earlier and initially while the sun's rays are less harsh and ideal for the lettuce, the tomato plants will be small, but as the tomatoes grow, you may be finishing up the lettuce. Consider planting carrots and Swiss chard too. Sun-loving herbs in the front.
Before you're done, you'll be building a bed that is not a rectangle, but bowed in front like a bow window, so you'll have more room to plant!