How can I stop this water from entering my basement?
For a complete repair there are 2 obvious directions to cover which you mentioned.  I'll go over what I would do in your situation.
Fix from inside
One product I would use is a hydraulic cement which can be found easily at your local home improvement store.  This stuff is great for fixing large leaks in the basement.... if you can find the source.  Hydraulic cement would be more permanent than a concrete filler or sealant and is commonly rated to 2000lb to 3500lb of hydrostatic pressure.  Stay away from your cheap concrete sealant you would find somewhere like Home Depot.  Most of these are water resistant, but not at all made for stopping leaks.  Assuming you do find your leak source and fill every hole, the main cause is still unaddressed.  For that we go outside.
Fix from outside
Fixing grading and downspouts will help a lot, however, in torrential downpour you may still get heavily saturated earth around your foundation, which is a bad thing.  Even worse, (depending on where you live) is water expansion as it freezes in the cracks.  This could seriously worsen the issue.
Probably one of the best (and probably the hardest solutions) is to use a polyethylene foundation wrap, something like this, in conjunction with a proper drain system at the bottom of the footing. Below is an example installation from the DMX installation guide found here.

A perforated drain pipe, crush rock, and proper drain or drainage field is necessary to keep the water moving.  Below is an example of a proper drainage system as provided by the EPA

Hope this helps, and best of luck!