As each my "mysite" is a new site collection using a Microsoft Site Definition, there is no no-code solution for automatically adding web parts to a page. (Well there is one no-code solution: Someone could sit in central administration add refresh the list of "mysites" and when he sees a new one he could log in and add the web parts, but I think that after a few days he'll be more than happy to install a wsp instead)
Feature Stapling is definitely the way to go. WebProvisioned will not work as it can only be Site or Site Collection scoped, if it could be WebApplication scoped then it would have been a great solution.
But notice that if what you want is to add web parts to the default page on each My site, then you'll run into the problem that the page isn't created until after your stapled feature has been activated, so you can't just add the webpart in FeatureActivated, the usual trick is to add a delegate control in the stabled feature which will the activate the third feature when shown, remove itself and redirect back to the page.
Another option is to create a new welcome page as described in SP2010 "MySites" – Part Four: My Content