Is it possible to dynamically update the symbology of a published map service?

Yes, it is possible to dynamically update the symbology of a published map service.

In ArcGIS Online, however, dynamic layers must be used to dynamically update symbology of a published map service. Dynamic layers can be configured after the map service is published.

Without dynamic layers, changes to symbology must be made on the layer in ArcMap before it is published as a map service.

Note:
Symbology is dynamically updated to display data in real-time, and to change the appearance and behavior of each layer. 

Although dynamic layers are enabled through ArcMap or ArcGIS Server Manager, changing the symbology of dynamic layers is typically done through code such as with the LayerDrawingOptions class for ArcGIS API for JavaScript. Refer to ArcGIS API for JavaScript for more information on map services with dynamic layers enabled.