the only way i could think of is creating a feature that encapsulates any webpart that will add extra chrome settings that will overwrite the webpart to show your styles/branding!
for custom webparts obviously that is easy as you just add the settings in the chrome section that will ammend the title colour ect for you and will save the layouts regardless if you move it to a different zone or not! this is obviously done through code ;) when adding the extra settings for as you put it a logo in the title!
for ootb webparts that is different as you dont have custome code so you would have to use the feature way to force styling/branding within the chrome so that its visible in the edit mode! I havent done it myself as neva needed to do this! most that i do is custom webparts so all can be branded individualy!
to me styling is the right word as branding (colour scheme, logo,main menu)is ment to be a global thing accross all pages! styling can be to an individual page. Doing at an individual level will be hell to maintain accross the site!!!
so if your looking to make high maintance than go for an individual level! if im wrong and that you want to just ammend the webparts slightly like adding logos to webpart titles ect than this is somthing else... if its custom webparts than that is easier but if its ootb that is somthing else and requires more thought as you would need to encapsulate each individual webpart what wouldnt be an easy task!
if you go for custom webparts as i mainly do than that is the best method for what you want, code in all the settings you require to show up in the chrome within edit mode. your codebehind that should handle (cutom code ;)) what you want to do with it like the logo example to be placed within the title! attach a css file to each individual webpart that can easily set styles / custom branding! now you have custome settings within the chrome and custom styles and branding for each individaul webpart regardless if you move them to a different zone or not! bingo