Assuming coolant type, level and all else to spec first.
I'd try back flush system. Treating it as three separate systems ie: radiator, engine block & heater. May as well replacing thermostat while at it, checking to see if it was sticking.
Note: Coolant system is self bleeding. Just Top off radiator first and fill reservoir to cold mark, while cold. If coolant system has been fully drained, I'll usually fill reservoir to hot mark this first time. Then run engine until normal operating temp reached, then let cool down until next morning (~12 hours). Each morning while cold (before starting) check reservoir adding coolant back up to cold level mark if needed. It usually takes two to three cycle until level holds the cold mark. Once this is completed and engine at normal operating temp; cabin heater should blow hot air. Heater will not blow hot if coolant level low or blockage in heater core(s) or lines.
Type of coolant: Toyota Red Premix or 50/50 Toyota Red/demineralized water. FSM recommends flushing 30K miles or 2 years.
