I have tried a method with a combinatorial group theory class, which is first to look at the universal quotient property relative to equivalence relations on a set. You explore this idea, and show that the set of equivalence classes is the answer you want and you derive the `first iso theorem' in that context. Exploring it to death if you like, with trivial do-able examples and constructions that students know. (e.g. different pairs (a,b) of integers giving the same rational numbers etc.) A function defines an equivalence relation and the equivalence relation defines a function and they are related. NB. no algebra at all in sight. This is strictly constructions on sets and functions.
The idea of the universal property is now centre stage i.e. where it should be. You can now ask if something similar is going to happen for groups and homomorphisms. The point is that it is not dividing out by a (normal) subgroup that is at stake here but by an equivalence relation (and that will not work of course). Equivalence relations seem to be more basic perhaps.
We all know the problem and the answer but the student has then something nearer to their previous experience. The equivalence relation does not work since although the quotient does seem to have an 'obvious' multiplication, that does not work and simple examples show it not to be well-defined (NB. 'Well definition' is a simple concept but students can (and do) find it very hard to grasp. This way, it is met as 'ill definition' first. The notion of well definition is perhaps not understood because it is usually presented as being a solution to a problem that the student has not ever met themselves.)
You now examine what goes wrong and get to the idea that you need a congruence not simply an equivalence relation. (Here I have used a categorical approach without the use of the term category, and really looked as a congruence as being an equivalence relation 'internal' to the category of groups... and no need to mention categories unless you feel like it. You can make the transition from equivalence relation to congruence in any way that seems appropriate for the background of the students.) This is the hard bit, not cosets, and it is hard, but sort of avoided in the usual treatment.
Now normal subgroups can be shown to be a reformulation of congruences and you can flip from one to the other and back again with no loss of info.
I like this treatment as the cosets only appear at the last moment, and then are the group theory analogue of equivalence classes. (If we have not got those across before we do cosets then there is no hope!)
This treatment also concentrates on the algebraic details that really need understanding. I do not mean group theory details as they are more specialised. We have equivalence classes, well definition and a universal property, three big ideas.
Normal subgroups come out as being natural.
Did this approach work? Not all the students could handle the idea of cosets, but they did seem happier with equivalence classes, well definition etc, and also seemed to like the universal property idea, which they met in various other contexts (product groups, free product, free group, etc.) in that course.