Excellent question!
In short, there are two logical possibilities to explain the data:
- There is dark matter and a cosmological constant (standard model)
- Gravity needs to be modified
Interestingly, both possibilities have historical precedent:
- The discovery of Neptune (by Johann Gottfried Galle and Heinrich Louis d’Arrest) one year after its prediction by Urbain le Verrier was a success-story for the dark matter idea.
(Of course, after its discovery by astronomers it was no longer dark...)
- The non-discovery of Vulcan was the a failure of the dark matter idea - instead, gravity had to be modified from Newton to Einstein.
(Funnily, Vulcan actually WAS observed by Lescarbault a year after its prediction by Urbain le Verrier, but this observation was never confirmed by anyone else.)
So basically you are asking: are we in a Neptune or a Vulcan scenario? And could not the Vulcan scenario be more credible?
The likely answer appears to be no. Modifications of gravity that seem to explain galactic rotation curves are usually either in conflict with solar system precision tests (where Einstein's theory works extraordinarily well) or they are complicated and less predictive than Einstein's theory (like TeVeS) or they are not theories to begin with (like MOND).
Besides the gravitational evidence for dark matter, there is also indirect evidence from particle physics. For instance, if you believe in Grand Unification then you must also accept supersymmetry so that the coupling constants merge in one point at the GUT scale. Then you have a natural dark matter candidate, the lightest supersymmetric particle. There are also other particle physics predictions that lead to dark matter candidates, like axions. So the point is, there are no lack of dark matter candidates (rather, there an abundance of them) that may be responsible for the galactic rotation curves, the dynamics of clusters, the structure formation etc.
Note also that the Standard Model of Cosmology is a rather precise model (at the percent level), and it requires around 23% of dark matter. There are a lot of independent measurements that have scrutinized this model (CMB anisotropies, supernovae data, clusters etc.), so we do have reasonable confidence in its validity.
In some sense, the best evidence for dark matter is perhaps the lack of good alternatives.
Still, as long as dark matter is not detected directly through some particle/astro-particle physics experiment it is scientifically sound to try to look for alternatives (I plead guilty in this regard). It just seems doubtful that some ad-hoc alternative passes all the observational tests.