I had this problem. Does your dome light go out when you turn the key over? Check your connections really good on the battery, make sure everything is tight. Even take them off and clean them. My problem was my battery wasn't producing the cold crank amps for some reason. It would do it when it got really cold. But when I took it places to test it, it tested fine. I put a new battery in it and haven't had a problem since.
So maybe try another battery? Use one from someone else's car if you dont want to buy one. Just make sure its big enough to crank the engine. If thats a no-go, try checking the starter connections, or even take it off and have it tested.