It sounds like the issue you're dealing with here is schema locking and there a few different things you can try without stopping the whole server.
1. Try stopping the individual service either from ArcCatalog or ArcGIS Server Manager and then deleting the data source.
2. Disable schema locking for the service, the work flow is documented in this resource page.
http://resources.arcgis.com/en/help/main/10.1/index.html#//0154000005z9000000
3. Overwrite the service with the data you want, after that when the undesired data no longer part of the service, it will no longer be locked and you should be able to delete it.
What kind of data are you working with? For instance Is it a file geodatabase or SDE?
It sounds like the issue you're dealing with here is schema locking and there a few different things you can try without stopping the whole server.
1. Try stopping the individual service either from ArcCatalog or ArcGIS Server Manager and then deleting the data source.
2. Disable schema locking for the service, the work flow is documented in this resource page.
http://resources.arcgis.com/en/help/main/10.1/index.html#//0154000005z9000000
3. Overwrite the service with the data you want, after that when the undesired data no longer part of the service, it will no longer be locked and you should be able to delete it.
What kind of data are you working with? For instance Is it a file geodatabase or SDE?
If you stop the service are you able to delete the data source? What error message do you get when trying to delete it?
Try rebooting the server and see if it then lets you stop and delete the services.