Good question! The capability checking is probably done quite early in the loading process. By looking at /wp-admin/users.php you can tell that one of the first things to happen is current_user_can( 'list_users' ), so that one is clearly needed or you’ll get the “Cheatin’ uh?” warning. But right before that, /wp-admin/admin.php is included, and at the bottom of that file WordPress will call an individual action for each page, load-users.php when loading wp-admin/users.php.
This means you should be able to setup a function to add the capabilities needed to perform your tasks during loading of that page (given that the current user has sufficient permissions to begin with, naturally). Something like this might work when giving a user new capabilities on the users list and user edit pages:
function my_add_caps() {
// add capabilities here
}
add_action('load-users.php', 'my_add_caps');
add_action('load-profile.php', 'my_add_caps'); // might be needed if you somehow cannot edit your own user
add_action('load-user-edit.php', 'my_add_caps');
I wouldn’t worry too much about removing the capabilities though, once the page is loaded the added capability will have played out its part. Keep in mind though that you might have to add the capability for admin pages responsible for storing options, or any AJAX-request handlers, depending on how much capability checking is done by WordPress during validation/storing of options.