" I'd still quibble a bit here - you seem to be conflating "observational evidence" with "experimental evidence"."
To some degree I probably am, yes. Even so, if we have a dinosaur bone in front of us, we have that bone. We can poke it, we can hit our colleague with it, and we can scrape bits off and drop them in each other's tea. If we're excruciatingly lucky, we can dig out traces of organic material inside it and piss off a generation of paleontologists in the process. (So far as I'm aware, that's been done - not enough to do much with it, alas, but still organic.) The difference here is we can't do that with dark matter. The only evidence we have is far more indirect, and can be explained through a wide variety of mechanisms, few or none of which are amenable to direct testing, meaning something we ourselves can actively do. In the dinosaur case, we can at least dig up more bones, or find previous bones, scrape bits off those, and drop them in someone else's tea.
I think there is a very big distinction between these, though I do see your point.
"I haven't heard of a "gravity is different" theory that made accurate quantitative predictions of the CMBR data, where the dark matter theory did. Maybe I just didn't hear about it?"
Probably. If nothing else, you can get the CMB without too much issue from Brans-Dicke, from f(R) (no surprise there; it's effectively Brans-Dicke with a weird parameter), and if you play enough absurd games with an absurd theory you can even get things out of TeVeS which is a contrived relativistic form of MOND. If you write down a vaguely sensible bimetric theory -- and TeVeS is not really very sensible, but others are -- it seems likely we can get the CMB out of those, too. Braneworld theories give it happily, and Turok and Steinhardt's somewhat... eccentric ekpyrotic universe where two branes repeatedly slam together like cymbals with each slam kicking off a big bang, can also do it.
On a weaker scale, you can take GR but change the metric. Cosmology is built on the (Friedman-Lemaitre-)Robertson-Walker geometry, which is the second-most simple solution of GR there is. The simplest is Euclidean space. An FLRW geometry is a whole bunch of 3D Euclidean spaces stacked one on top of the other. It's slightly more complicated than that, since you can get closed FLRW (effectively a bunch of concentric, ultra-smooth spheres) and open FLRW (basically a load of saddles piled one on top of the other). There is good observational support for FLRW, but the same support can be given to a variety of particularly Bianchi universes, which are like an FLRW but slightly anisotropic. Control that anisotropy, and you've got a perfectly valid universe, with a slight directionality (which, intriguingly, Planck has seen in the sky -- though the form of anisotropy is actually not that easy to reconcile with simple Bianchi models). Until recently you could play games with Lemaitre-Tolman-Bondi metrics, which are like FLRW but lack the homogeneity, so that while around Earth everything looks spherical, away from us it is distinctly less so. In reality you still can use LTB models, but you have to be careful, and their main use (the observable effects of dark energy without having to introduce a physical dark energy or accelerating the universe) has been pretty comprehensively rubbished. (It's still not certain, since we haven't yet finished working out the perturbation theory properly, and without it any claims to be genuinely looking at the CMB and the oscillations in the large-scale structure should be taken with a bit of salt but, realistically... it's a very small bit of salt.)
And then we can assume gravity is the same but the problem is simply coming because even on galactic scales we're working with averaged motions (or, more concretely, a statistical mechanical system). On cosmological scales we can view things in three ways: a spatial average, an average across observations (these are distinct; one is the average of, say, the angular distance to objects of equivalent types, while the other is a straight spatial average), or statistical mechanics. Of these, unfortunately, we can't do the spatial average or the statistical mechanics -- so these are obvious, and necessary, directions for study. There has been a lot of work on the spatial average, none of it particularly convincing but some of it quite suggestive, and there is work on the statistical mechanical average, but that's hampered by the extreme difficulty of working with general relativistic statistical mechanics. Which is tough.
Anyway, yeah, you can get the CMB - and, more, the baryon acoustic oscillations which were formed about 12 billion years after the CMB but in the standard big bang model are intimately related - from modifications. The only problem is that those modifications do have to end up resembling FLRW so closely that the observations are practically indistinguishable, even if the underlying model bears no resemblance. That's tricky, and it's a major reason Lambda CDM holds as much support as it does.