Caroline, I can't speak to the SII, or if you have headers rather than the stock exhaust manifold, but I was able to get my starter both out and back in w/o removing it. I can't say for sure but once it was "free" I think I angled the back of the starter up. I had a friend hold it from the top and brought the shaft out and lowered it, shaft down. It went back in easier, did it by myself. I'm sure it would be easier w/the manifold off, but that requiers quite a bit more work to get to. Perhaps, if you just drop the exhaust pipes, from the manifold, you will get the extra room. If you are seriously considering removing the engine, to get it painted, everything gets easier to "do it right". Like you, I wanted my engine to be running and car painted, before doing the interior, top, putting on the chrome, lights and rubber moulding. Since all the lights and chrome had already been removed, the rubber is shot, and it's in old primer, it just made more sense. One of my main priorites is to be able to do most of the work, myself, and still get it on the road by summer. I opted to remove most of the "stuff" in the engine compartment, for rebuild/replacement, but left the engine in the body. I cleaned and repainted the engine compartment w/black rustoleum and touched up the paint on the engine w/1000* engine paint. (I'm probably giving some of the members a heart attack). Once I had the "stuff" back on and had it running, I could think about having it painted. It's now @ a local body shop for paint. Once it's back I need to rehook up all the electricals and do interior...etc. The underside of mine was pretty free of grease/oil/grime but my differential was covered in about 1/4" of crud. The sprays I used softened it some but were pretty worthless as far as removing it. I ended up using a puddy knife and used the sprays to clean it up after removing most of the crud.
A question I think you need to ask yourself is: Do you want a project or a runner? You could have a project, for enjoyment or cost, that may take awhile, if you do the work yourself. Or you can have a nice runner w/in a pretty short period of time. The difference is $. Think about it and make a plan of what you want to do, in what order. Whatever you decide, there is a wealth of information and people on this site, who can help you.
Ron