I don't know the precise answer (because it depends on the precise definition of an homology theory you may prefer), but I would ask the question in a slightly different way (giving out the CW-structures for a while). We might try to think of the problem in the same way we solve the problem of a topological Galois theory over a space X: we shall get a Galois correspondance
{covers of X}<->{representations of π₁(X)}
iff (the topos of sheaves over) X is locally simply connected. If X is not locally simply connected, we shall get such a correspondance with the toposic π₁(X), which will be a pro-groupoid, hence something different from π₁(X) computed in the usual model category of spaces. We might think of this phenomena as a non additive version of our question.
More generally, given a space X, we might ask when do the topos-theoretic invariants and the CW-invariants (i.e. the ones obtained using the classical model structure on Top) agree. The interest of this point of view is that this will be a local problem on X, and that it will provide systematically two ways to look at a (co)homology theory: in the model category of spaces, or in the homotopy theory of (∞-)topoi.
As far as I understand all this, the only thing we use in the CW-structure is the property of local contractibility: if X is locally contractible, then we can consider the set O(X) of contractible open subspaces of X (ordered by inclusion). We have then that X is the homotopy colimit of its contractible open subspaces (in the usual model category of spaces, but also in the setting of ∞-topoi). Hence the homotopy type of X (as a space and as a topos) is just the nerve of O(X), which has a canonical CW-structure
(but I don't know how to prove that X has a CW-structure itself), so that uniqueness of (co)homology will hold on such an X (assuming some nice descent properties). The idea is that we can weaken these local conditions.
To set the general problem, we might fix a nice left Bousfield localization of the model category of topological spaces, which I shall denote by S. By nice left Bousfield localization, we might mean that it is obtained by a nullification (i.e. by inverting a map of shape A->pt). We might think of S as the homotopy theory of (n-1)-groupoids (in the case A=Sⁿ, for 0≤n≤∞), but we might also take A such that S corresponds to CW-complexes up to Quillen's plus construction, which is more related with our problem with singular homology. The reasons why I suggest to consider only nullifications are that 1) they are nicer because they lead to proper model categories (at least in Top), which makes computations easier, 2) in all the definitions, we shall only deal with weak equivalences of shape X->pt. The idea is to study the theory of "topoi relatively to S".
Given an ∞-topos X, let us denote by Sh(X) the ∞-category of stacks on X with values in S. We thus have Sh(pt)=S. Let us say that X is S-aspherical (or, if you prefer, S-acyclic...) if the constant stack functor S->Sh(X) is fully faithful. And let us say that X is locally S-aspherical if there exists a generating family in X (if X is a topological space, this means a basis of open subspaces) made of stacks U over X such that X/U is aspherical. For a general X, the constant stack functor c:S->Sh(X) will always have a pro-adjoint, and the nice thing is that this pro-adjoint will be a genuine left adjoint to c if and only if X is locally S-aspherical. In other words, we then have a functor à la Artin-Mazur
{∞-topoi}->Pro(S)
(which has a right adjoint; see 7.1.6.15 in Lurie's book on higher topoi),
and I guess it will induce an equivalence of ∞-categories of shape
{locally S-aspherical ∞-topoi}=S
(for this, consider {locally S-aspherical ∞-topoi} as localized by S-equivalences, i.e. by maps which become invertible in Pro(S)).
Thus, for a topologcal space X, we have two ways to send it to Pro(S): consider the pro-S-homotopy type associated to Sh(X), or consider X as an object of the categoy underlying the model category structure on Top underlying the definition of S.
Then, topological spaces X whose associated ∞-topos are locally S-aspherical are precisely the one for which the two ways to see them in Pro(S) coincide. If S is the homotopy theory associated to Quillen's plus construction, then we get that, for any topological space X which has a basis of open subspaces U such that U->pt induces an isomorphism in (pro)homology with constant coefficients, the topos theoretic singular (co)homology and the "usual" singular (co)homology (computed using Hom's in (pro-)spectra) will coincide. But otherwise, they won't, and we might expect to get explicit examples of non-agreement in this way.
[additional comments and precisions]
What I call the topos theoretic singular cohomology is just the sheaf cohomology with coefficients in the constant sheaf Z (which is the same as taking the global sections of the image of the K(Z,n)'s by c:S->Sh(X)). If you consider a topological space X, then the topos-theoretic singular cohomology of X will be a cohomology theory satisfying excision, which will coincide with usual singular cohomology for locally contractible spaces (and more generaly, locally S-aspherical spaces, where S denotes the homotopy theory of spaces up to Quillen's plus construction). For homology, you will have the same picture, except that it will take values in pro-abelian groups in general (except again for locally contractible spaces, etc): consider the associated pro-space, and take its usual homology. This toposic point of view thus gives you a cohomology theory which coincides with singular (co)homology for good spaces, but won't agree for a large class of them. All this story applies for any (co)homology theory which preserves homotopy colimits (which implies the Eilenberg-Steenrod axioms).
As for the existence of the pro-adjoint of c:S->Sh(X), this is because any accessible left exact functor has such a thing (as proved in Lurie's book). The pro-homotopy type associated to X is then the image of the terminal object of Sh(X) by this pro-adjoint.
I should mention as well that the theory of pro-homotopy types of topoi is treated in section 7.1.6 of Lurie's book on infinity topoi (in the case where S is the usual homotopy theory of infinity-groupoids, but the same arguments should work in the generality I suggested here). I cannot resist to mention that this kind of point of view can be seen (after Lurie) as a conceptual way to look at shape theory, but this is also (higher) Galois theory in the sense of Grothendieck (such a point of view is also mentionned in the work of Toën and Vezzosi on higher topoi): in the case where S is the homotopy theory of 1-groupoids, one gets exactly the theory of the fundamental group as developped in SGA1 (and later by Leroy, Moerdijk, etc).
[Conjecture]
I propose the following conjecture as an answer to the initial question (and the constructions suggested above give at least some evidence, not to say an idea for a strategy of proof).
The largest class of spaces for which the Eilenberg-Steenrod axioms determine singular homology consists of the topological spaces X satisfying one of the following four equivalent conditions.
1) for any open subspace U of X, sheaf-theoretic homology and usual singular homology coincide;
2) the open subspaces U of X such that the sheaf theoretic singular homology of U is trivial in degree >0 form a basis of open subsets of X;
3) the open subspaces U of X such that the usual singular homology of U is trivial in degree >0 form a basis of open subsets of X;
4) the open subspaces U of X such that U_+ is contractible form a basis of open subsets of X.
Best Answer
I was a heavily involved TA for such a graduate course in 2006 at UC Berkeley.
We started with a little bit of point-set topology introducing the category of compactly generated spaces. Then we moved into homotopy theory proper. We covered CW-complexes and all the fundamental groups, Van-Kampen's Theorem, etc. From this you can prove some nice classical theorems, like the Fundamental Theorem of Algebra, the Brauwer Fixed Point Theorem, the Borsuk-Ulam Theorem, and that $R^n \neq R^m$ for $n \neq m$. I felt like this part of the course went fairly well and is sufficiently geometric to be suitable for a first level graduate course (you can draw lots of pictures!).
At this point you can take the course in a couple different directions which all seem to have their own disadvantages and problems. The main problem is lack of time. A very natural direction is to discuss obstruction theory, since it is based off of the same ideas and constructions covered so far. However this is not really possible since the students haven't seen homology or cohomology at this point!
Instead, for a bit we discussed the long exact sequences you get from fibrations and cofibrations. You could then try to lead into the definition of cohomology as homotopy classes of maps into a $K(A,n)$. But this definition is fairly abstract and doesn't show one of the main feature of homology/cohomology: It is extremely computable. Still, I could imagine a course trying to develop homology and cohomology from this point of view and leading into CW homology and the Eilenberg-Steenrod axioms.
Another direction you can go is into the theory of fiber bundles (this is what we tried). The part on covering space theory works fairly well and you have all the tools at your disposal. However when you want to do general fiber bundle theory it can be difficult. A natural goal is the construction of classifying spaces and Brown's representability theorem. The problem is that the homotopy invariance of fiber bundles is non-trivial to prove. You should expect to have to spend fair amount of time on this. It is really more suited for a second course on algebraic topology.
The main problem with all of these approaches is that it is difficult to cover the homotopy theory section and still have enough time to cover homology/cohomology properly. You know this has to be the case since it is hard to do the reverse: cover homology and cohomology, and still have enough time to cover homotopy theory properly.
What this means is that you'll be in the slightly distasteful situation of having bunch of students who have taken a first course on algebraic topology, but don't really know about homology or cohomology. This is fine if you know that these students will be taking a second semester of algebraic topology. Then any gaps can be fixed. However, in my experience this is not a realistic expectation. As you well know, you will typically have some students who end up not being interested in algebraic topology and go into analysis or algebraic geometry or some such. Or you might have some students who are second or third year students in other math fields and are taking your course to learn more about homology and cohomology. They would be done a particular disservice by a course focusing on "homotopy first".