From your question I assume the transitions between different polymer conformations are slow and that's why you need enhanced sampling. In any case, enhanced sampling unfortunately provides no solution to combinatorial explosions and should mainly be used in order to not waste time on local minima.
There are quite a few enhanced sampling methods and here I am going to list the ones which I think could help you the most (not in any particular order):
1. Replica exchange (as mentioned in your post). This is probably the enhanced sampling method to use in general. Its main problem is that the number of replicas increases with the size of your system - therefore tempering only certain crucial parts of the potential energy function is highly desirable.
2. Metadynamics. This is also a very popular method to explore different configurations and it works by pouring computational "sand" onto your potential energy surface, which results in uniform sampling at infinite time. Of course, this does not happen in practice and there are plenty of convergence problems with the method (although this could be said for literally any sampling method), which have partially been resolved in the past few years, mainly with well-tempered metadynamics and adaptive metadynamics. However, this method relies on you having only a few reaction coordinates, which may or may not be applicable to your system.
3. Rigid body dynamics. This is not an enhanced sampling method per se, but you can use it to constrain"fast" degrees of freedom, so that you explore the "slow" degrees of freedom more efficiently. In effect this amounts to coarse-graining your system and might need changing your potential energy model, which may or may not be helpful. Again requires knowledge of what the important degrees of freedom are.
4. 28
Simulated annealing. If you are not interested in statistical mechanical properties, and mainly in minimised structures, you can use this method to heat up your system and slowly cool it down in order to find a good minimum. Sounds like you already considered this option, but this leads us to...
5. ...Population annealing (also known as sequential Monte Carlo). This method is a parallel/path-integral-like extension of simulated annealing and is equivalent to running a lot of simulated annealing schedules at the same time, but only picking the best paths - so it is much more intelligent and efficient in this sense. You can also make the temperature range adaptive, which you can't usually do with replica exchange.
6. Nested sampling. Depending on how rough your potential energy function is, you might want to consider nested sampling. I have only ever seen it be used with nonbonded systems though, so I am not sure how well this carries on to polymers. In any case, it is an interesting global sampling method (but its scaling is not necessarily very good). I mainly added this out of interest but it could be worth considering.
As I mentioned, replica exchange is your best bet if you are not sure what to do, but the other methods can also be very useful depending on your problem. I am not aware of a single reference which contains these methods - I would mostly search the primary literature for these. It is also worth saying that most of these methods are actively under development, so you might have to read around :) 7