With any of the web APIs, reordering layers is simply a matter of manipulating the Map object's layer collection. I strongly agree with Michael and Brad, however, that allowing users to pick and choose from many layers usually makes for a poor application. An exception would be if you have a "designer" or "administrator" role, where users within this role are experts that make meaningful subsets of layers to share with the bulk of the application's users. Examples of such an approach can be seen in Esri's Explorer Online or SharePoint products. Another exception would be if the repository of layers to choose from is small. If your application does not fall into one of these categories, I would suggest that you are doing your employer a disservice by not pushing back hard on this requirement.
On the subject of the acceptability of browser plugins, this is less and less of an issue in government as more agencies, including the US armed forces, have approved use of Flash and Silverlight in application development. Plugin adoption is recent for many departments and agencies, and in some cases is not widely known by their employees. So if you receive an indication that using a plugin is not an acceptable approach, you or someone on your team should double-check this against the agency's technical guidelines.