How to update the Service Definition of a Feature service on ArcGIS Online (AGOL)?

It appears to me that it is not possible at the current release of AGOL.

What you can do is that you can just use another name when creating an .sd file and then rename the .sd file manually. It works fine then to use the Update link in ArcGIS.com to upload the .sd file which should have the same name. Moreover, .sd file is just an archive which you can unpack and explore.

However,it seems to me that there is no way to update just the symbology for a service on AGOL without not uploading the data again, since it is .sd based. You probably know that one can change symbology for a service directly in ArcGIS.com Map viewer, but there are some limitations on what you can do.

PS. If you will by any chance work with data you want to create map cache (Tiled Mapping capability for a service), create tiled package in ArcMap first by enabling an option, and then upload it to AGOL without burning credits that are taken when caching.

For anyone finding this now, the landscape has changed slightly since this was first answered. It is now possible to update your symbology directly through ArcGIS Online. If you go to the feature layer item in question and click the Visualization tab, you can update the symbology by clicking on the the style button of the layer in question and saving the layer.

You can even create a second view of the data with different symbology by creating a Feature Layer View. This lets you create another configuration of the feature layer meaning you can change the symbology, add filters, alter editing permissions, etc. but not create a second version of the data as it still looks at the data from the underlying feature layer.