I have been using an approach similar, breaking tasks down into chunks (subs) and also writing the interface to a module before coding the module. Yes, I am also trawling through CPAN so I don't reinvent the wheel. These things I feel are working reasonably well for me.

However.....I'm still finding that halfway through the coding I'm either having that 'lightbulb' moment and scraping half the code and starting again or , as I mentioned in my original post, I code myself into a corner...usually with unwieldy data structures that get more out of hand as I progress.

Maybe I need to 'play' with my sub templates a bit longer before I start fleshing them out with the actual code?