Kareos

I was envisioning a dedicated button, but if you're set on the 2 button approach, then I would think that could work. An alternative would just include a timer on the block button itself. If the player presses block at the right time, he'll automatically parry. That being said, as long as you explain the controls to the potential player and it doesn't make him do anything stupid with his fingers, he'll figure it out. 

Personally, one of my favorite elements of a simple beat 'em up is the ability to counter an attack. Think of the Lord of the Rings Two Towers / RotK (and countless others, I suppose) as an example. Nothing beats a good parry / riposte insta-kill. Nothing to say that can't be added into a simpler hobbyist build.

As for your difficulty progression I would say don't be afraid to have the game scale, but throw in a few old enemies along with the meaner, palette swapped baddies. That way, the player can have a feeling of transcendence over the once tough foes.