Just not too long ago did the same with my 73 Dart with a 318 and a mini starter out of a Ram 1500.
Had to pry the engine over to the passenger side as far as possible, and they are SERIOUS about the header going striaght up and then forward.
After trying and trying, it finally found the one angle that it slipped in.
(it seems like I remember tilting the motor to the passenger side also.)
Passenger side was a breeze.
The starter problem sounds suspicious, as mine went in perfectly without any clearance issue's at all, and with the original starters hardware.
Are you sure you have the right starter?
I used Remflex gaskets also, because I darn sure didn't want to have to mess with it again for a gasket leak down the road.
Now that it is done I'm happy with it, but I don't know what it would take to get me to do it again. :-)