The short answer is no, you don't need all the gems first.
Highlight for tip on how to kill the sharks:
The scout doesn't have to be really close to the shark to throw the harpoon. So, as soon as your scout harpoons the shark, move him a little bit away so the shark doesn't get him, but let him go again quickly so that he can throw out another harpoon. I've killed a shark using only one scout using this method.
I must have the slowest mouse or something because I have been trying to kill sharks for the last hour using this method, and I have "sacrificed" it must be 100s of scouts! OK, they are only cartoons on a screen, but it really bothers me! I always lose at least one of the two immediately, and I can't yank the other one out fast enough to keep him from getting eaten on the second shot! Also, the shark heals so fast that I can't get the scout back in the water to attack for the second shot fast enough before the shark is almost completely healed! I have a nasty feeling I won't be finishing this game completely. I am extremely discouraged and going to quit playing for awhile.
One thing that might help you would be building more scouts lodge. Don't get discouraged! Continue to move your scouts away from the shark when he attacks and towards the shark when he retreats! Good luck