Can I change a course theme without rebuilding the entire course from scratch?
Oh yes, for sure, that is the great thing about Evolve!
To change the current theme - just go to your course, go to Theme in the menu and then make changes. All courses using that theme are changed simultaneously. All courses reference the same theme.
To select a totally new theme for a course, go to Theme then Select Theme, top right.