Regarding nature being random, there is no physics that suggest it is. "The wavefunction evolves deterministically", it's just that we as non-fundamental particles can't observe all amplitudes realized at once. (I suppose if you're a Copenhagen believer, the idea of collapse is non-deterministic...) Also, being uncertain about a system's future because one does not know the system's initial conditions doesn't mean the system is random.

For free will: http://wiki.lesswrong.com/wiki/Free_will_%28solution%29 (My paraphrased tl;dr for programmers in case you're a Sith: you can't possibly have any sort of will, free or otherwise, in a non-deterministic world; furthermore, we can create narrow AIs whose deterministic function is to search a space of possibilities and if it finds what looks like a good solution, it settles on that, or we can instruct it to search for other solutions, and this is what our will somewhat looks like from the outside--a search algorithm through future possibilities, some of them just as impossible physically speaking as our AI picking a solution that isn't past the stopping threshold--while what it feels like on the inside is that "we could realize any possibility[, if we felt like it]")