Video Tutorial: Walkthrough (bow)
First run to where there are a lot of flying Storm Beasts, as you approach they will start attacking. Run and roll as fast as you can to the end of the big outstretched cliff on the left. You will see the Stormruler, take it out and run back to safe zone. Equip it, and go back towards one of the safe zones. Lock on to the Storm Beasts and attack them with your new sword (awesome right?). Keeping Thief's Ring equipped is very handy. The Storm Beasts will only attack you if they are close, and if they are attacking you, then they are close enough to be hit with Stormruler. Try to stay in the area where you got the Stormruler, as the Storm beast don't fly over this area and it's safe from them. It's also where the Storm King flies over for his first swoop and you can attack him from here. The pillars are also safe points.
Damage does increase when wielded with 2 hands. When there are only around four Storm Beasts left, the boss will fly closer to the ground, run quickly to a safe zone. He will swoop over the area from one side to the other. When he approaches, hide behind something and wait for the flying stingers to end, then step out and lock onto the boss, attacking him with sword. You should easily be able to land two or three hits on each pass.
Remember that you can lock onto about 5 segments of him, 3 in a line on his body, and his 2 wings. So switch between them as necessary to continue hitting him. Once he has gone past you go back to a safe zone or try to kill any other stray Storm Beasts. When the boss comes for another round hide in a safe zone and repeat the pattern until he falls. Be sure to pick up the two Chunks of Cloudstone, located at the far side of the cliff, since they are only found as a treasure here.
Similar to the previous strategy, although you don't need to use the Stormruler. Instead, use a ranged attack of your choice. Using the Lava Bow, hide behind the house. The Storm King will die in 2-3 passes.
Points 3 and 6 in the map are safe zones. Hiding in these areas will ensure your safety against the Storm King's attacks.
You can use the Soul ray spell while he is flying overhead, boosting your power with the Cleaver Rats ring and the Morion Blade combo. It is however very dangerous with no safe zones to hide in. Rolling back and forth as the spikes come at you does work, but it is one of the more difficult dodging methods.