Allow contributors to add categories, but not delete

Since the category widget on the post page only lets you create categories and not delete them, you could just hide access to the main category editor page for this user type, and allow them to still create categories within the post editor.

You could do this with CSS or javascript, something like

$('ul.wp-submenu a[href="https://wordpress.stackexchange.com/questions/14060/edit-tags.php?taxonomy=category"]').hide();

You could target this to a specific user group by passing the user capabilities to javascript using script localisation.