Depends on both the type of starter AND the brand of headers.
Some headers require mini-starters, but you can usually change those out without removing the header. Some headers still work with the giant stock starters, but those almost always require the header to at least be hanging (not fully installed) in order to remove the starter.
And of course even header/starter combo's that should allow the starter to be removed without messing with the header can be compromised by other mods- larger torsion bars, aftermarket oil pans, 4 speed linkage, etc.