Visio 2010: replace a shape
I asked this question directly to the Program Manager of Visio 2010 at Microsoft during an internal MS event on campus and the answer was: "This is not possible". I have been missing this feature since Visio 2003 and hope that it will be finally added in the next version of Office.
An update: this feature was added to Visio 2013
See: https://docs.microsoft.com/en-us/archive/blogs/officedevdocs/change-shapes-in-visio-2013
The "Change Shape" feature was introduced in Microsoft Visio 2013. Demo: