It’s possible. You could play a few tricks with CSS to replace the header image based on the category.
Likewise with the sidebar, using custom CSS for each category, you could hide elements and display others.
You’ll need to hack your template to add a “<category>.css”, where WP will be filling in the <category> part.
