You can sell them any time, before or after you get the Pyramids - the same applies to Barracks with Sun Tzu. Just cycle through the cities and right click the improvement if you've waited until later. If it was hand built then you'll have a sell option in the menu.