After my 2 heater core jobs this year, they aren't so bad. It was about 4 hours labor, over all.
The cooling system isn't tough. I'm sure there is no engine blockage (Or else would be the last of your problems). Radiator flow / air flow over the radiator (By design perfected), two main hoses, heater hose and core (Got a wet floor? Does it fog up the windows instantly when you turn on the heat?)
Then you'll have to worry about how hot the engine gets. If the engine runs too cool for the heat to work (As happened in my Loyale this year) replace the thermostat. Running without a thermostat won't give you heat, it will take it away.