[deadBird]

How do you know it's not the battery? Some batteries can have dead cells.

First off, I'd completely clean off your battery terminals.

Second, check/replace your spark plugs & spark plug wires.

Third, you may have a defective crankshaft sensor or PCM valve. Or you have just have to clean them.

After that, check all the wiring to the solenoid & starter. My guess is the spark plugs.

How does it run once you get it started???