I recommend using OBS. Lots of recording options and completely free.
You can still stream with <1mbps upload. 500 bitrate is normally acceptable quality. Theoretically you should be able to stream at 500 bitrate with a 0.5mbps upload.
Other options for local recording are Fraps and Dxtory. Both cost about £30.
The main issue with Fraps is that it has a pretty heavy performance hit on your PC, and Dxtory produces enormous files. I think OBS is the best option.
You can try OBS using the NVENC encoder, which is what Shadowplay uses (it runs on a dedicated chip on your GPU, not your CPU). You might be freezing because Shadowplay is recording at a crazy bitrate, you can try setting it to 10000 for great quality or even as low as, say, 5000 in OBS and it'll still look fine. You'll probably want to set it to downscale to 1280 x 720 as well. There's a good chance this will fix your issues.
Good luck!