Why would drawing both the map and the units at the same time be impossible? Is it because drawing the entire map in one go is more efficient?
Regarding drawing units that are not covered by anything:
If you only want to redraw part of the screen at each frame, I'd suggest animating the units (given than the user does not scroll the map, otherwise you'd be back at step 1 and re-drawing it entirely) by saving the screen rectangle on which you're about to draw each unit, so that you can "cancel" the drawing by restoring this rectangle when you want to draw the next animation frame. (In this case, make sure you cancel the drawing of each unit in reverse order.) I don't know if it's technically possible, but I think it'd be fairly efficient.
Another way would be to redraw all the tiles and units which are totally or partially covered by your unit, and those that they themselves cover, all the way up to the top of the screen (in reverse order, of course), but it may end up even slower than redrawing everything if not careful enough (ie. some things might be redrawn twice).
For units that
are covered, the simplest way would be to redraw what's covering them once the new frame is ready, but you'll end up redrawing things from top to bottom (as CodertheBarbarian suggested).
The most optimized idea which I can come up with right now is to draw "static" objects (eg. ground, non-animated buildings, etc) and "dynamic" objects (roughly animated things) to different layers. Then, when you want to do the regular update the screen, you'd redraw the dynamic layer and perform the layer merge with the static layer when copying it to VRAM. This way, you only have to perform the merge on the animated areas, which I think is pretty efficient.
I have almost no knowledge of the platform however, so I hope these suggestions make sense.
Edit: I even forgot to tell how great this project looks. I'm amazed that so much can be achieved with pure assembly. Good job!