How to clean such a bad shapefile for routing?

You can use GRASS to do some cleaning. I think you need to break those vectors remove duplicates and then snap them. For that there is the v.clean tool with the options break, rmdupl and snap .

Within PostGIS, try ST_SnapToGrid to snap vertices to a virtual grid. You need to to some detective work to determine what snapping distance to use. It could be a 0.01 (1 cm), or 1.0, etc.