My suggestion is to build a custom function, based on the source code of paginate_links(). More specifically, you need to modify the following conditional checks so they ignore the current position and always display the link:
if ( $prev_next && $current && 1 < $current ) for the “Previous” link and
if ( $prev_next && $current && ( $current < $total || -1 == $total ) ) for the “Next” link.
You may place it in your theme’s functions.php file or in a plugin and call it as you would call paginate_links() (same parameters). Just make sure to name the new function different or you will get a PHP error “can not redeclare function”.