Update : Was about to give up flushing the heater core because I couldn't get the hoses off but I eventually got help and got them off. Lucky I did because it was filthy when I flushed it.
Dumped the intake pipes into hot water to loosen the sludge and scrapped it off with a popsicle stick. Much better now.

Filled up the heater core with new coolant while I had hoses connect to the heater pipe to save time filling up later.
Installed new air filter (old was was dirty too), connected everything back up - refilled and bled.
Now my engine doesn't blow any smoke or anything, runs and idles fine. Is there a way I can check if there's build up in the engine?