MXD is a closed ESRI format (paths are definitely not stored in plain text), and as far as I'm aware of, there are no standalone programs that allow editing without an ArcGIS Desktop license (or similar). As you have ArcGIS Server, you have an ArcObject license, so you could technically write a simple app that would update the paths for you. However, it may be a lot less trouble to guide the client/end user through repairing the data source.
You can also look at similar previous thread for a reference: How do you deal with (repair/avoid) broken MXD\LYR paths?