I can't preach this enough, but you HAVE to have clean connections on everything to have a chance on it starting! Clean the battery terminals and the cables with one of those little battery terminal wire brush cleaners, clean all of the connections on the starter relay while the battery is disconnected, making sure to put all terminals back in the right place! Clean each ground that goes to the engine block, the negative battery lead and the block to firewall connections as well!! This has been the solution to problems just like this many more times than I can count!!!
