Simply put, power begets more power (skill).
The best way to increase your Power skill is by engaging in combat through normal play. You are correct that your starting weapons are absolutely terrible and parkour is the intended method of play for this stage in the game. As you progress in the game you will slowly find weapons at higher Survivor levels which can be used to increase your Power level more easily.
To increase your Power skill you should focus on increasing your Survivor level. This is done through enduring the night without sleep, turning in GRE airdrops, and completing quests. As stated, the weapons you find are tied to your Survivor level so you will be more likely to find powerful machetes, crowbars, and sledgehammers.
When you start to find strong weapons you will be able to take on zombie hordes more easily while engaging in normal exploration. Clearing out safe houses and completing escort quests are two common situations where you'll be forced into combat and increase your Power skill through "normal" play. Now, with a high Power Skill you'll be stronger and more equipped to complete quests, collect airdrops and explore at night. See where this is going?
In short: Survivor Skill leads to better weapons leads to higher Power Skill leads to higher Survivor Skill
There is one other way to quickly earn Power skill points: Zone challenges. These challenges are encounters with survivors which offer trials of escalating difficulty. The two main kind of challenges are parkour challenges and combat challenges. As you might expect, combat challenges offer Power Skill experience points as a reward. These can provide a quick boost of experience points if you want to go go through the encounter.
As a bonus, these challenges can often be completed at any level; the game will provide weapons for you so your character will be able to easily deal with the zombies in these challenges. For instance the challenge Dying Lunch in the slums will temporarily provide you with a firearm and ammunition so you'll be able to survive regardless of your level. Similar challenges may provide you with enhanced throwing stars or an electrically charged machete - regardless of tool you'll be killing biters with ease.