Error in table 'sys.sysbinobjs' on master database
There's nothing you can do to fix it, I'm afraid, without a backup, you can't fix errors in system tables like this and I actually would've been surprised if installing SP4 would've worked.

The best (and probably only) way to resolve this is to create a brand-new, clean install of SQL Server somewhere else, then restore all of users database there, and script out your logins and jobs etc. to the new site. 

Not ideal, I know, and a bit time consuming perhaps, but easy to do and it'll definitely solve your problem. You might be able to sell it as/use it as an opportunity to upgrade everything, spec the system exactly who you'd like it and get everything updated. There will be some downtime (but this can be minimised).

This is similar to your situation (but perhaps worse) and Paul Randal's reply puts it quite succinctly. This on SSC is another similar one, but not answers (except a confirmation that there's not a lot you can do). Finally, this MSDN post explores the problem as well - same conclusion.