Right, Redirection plugin itself requires ‘manage_options’ capability. But “Tools” menu is protected by ‘edit_posts’. Add ‘edit_posts’ capability to your role and “Tools” menu will appear with “Redirection” and some other submenu items together.
My test role contains just 3 capabilities: read, edit_posts, manage_options
and such user sees Tools->Redirection menu item.
What if you deactivate all plugins except redirection? Will it become available?
Thanks for the note about PHP warnings. I fixed the problem.