Normally I wouldn't be bothering with a program this old, but it's the only Premiere Pro version I've had any luck with.
I combined the Adobe Photoshop CS5 bottle provided by Crossover with the Premiere CS4 installer file and managed to install the application (along with Encore CS4 and OnLocation CS4). The installer was kind of odd. It seemed like there were objects missing and there were no actual clickable buttons, so I had to navigate it with the tab and enter keys, but it worked fine otherwise.
All the apps showed up on my computer (OS Ubuntu 16.04 LTS). OnLocation worked fine. No problems there. I'd imagine that Encore would work fine as well, but it isn't able to run in trial mode and I don't have a subscription. Premiere would show the usual boot screen, grey out when attempting to load PlayerMediaCore.prm, and completely crash when loading SolidComposit.AEX, showing the 'report bug' pop up. I'm not sure if this is due to the limited capabilities of my machine, but it seems to be an improvement over past attempts.
Please let me know if there is any more headway (although I don't expect any with software this old).