Perhaps a better solution would be to increase the weapon damage to 4w
Erm... no. Let's use your example, a large executioner's axe, 2d6 and brutal 2, meaning it does at least 6 damage, i.e. 4 x 6 = 24 damage, with no strength modifier (the same as 3[W] and brutal +1)
Now look at the averages: A brutal 2 axe has an average of 9 damage, i.e. 36 damage on average with 4[W].
With 3[W] and increase of brutal by one, you get an average of 10 damage, i.e. 30 dmg with 3[W] and brutal +1.
And now the maximum damage: With 4[W], it's 48 damage, with 3[W], it's 36.
Your version is strictly more powerful than Stalker0's idea. If we now compare it to the results of the 3[W] without any change (the axe again):
Min. Dmg: 18 damage.
Avg. Dmg: 27 damage.
Max Dmg: 36 damage.
We see that the increase of brutal by one increases the minimum damage (+6) and the average damage (+3). Your solution increases everything.
Looking at the effects of the increase of brutal, compared to a basic attack (again with no Str modifier added: Min 6, Avg 9, Max 12), it's worth less than an extra basic attack (esp. if you do have a positive Str mod), so it's about half an action... which sounds right, looking at Comeback Strike (which allows you to heal, i.e. worth about an action), as the +1[W] from Brute Strike is less than an action - with the extra bit of brutal, it gets to be worth as much as one action (approximately), as it has to compensate for the Strength modifier.
Cheers, LT.