Are shortcode functions applied while rendering the content, or are they executed and stored with the post content?

I don’t know in what exact order filters are applied to the_content(); and whether that’s early enough, but if it doesn’t work for you, I believe it is safe to assume that you’re right in thinking that the shortcode is applied to late.

From /wp-includes/shortcodes.php (line 296, wp 3.2.1) it can be seen that shortcodes are naturally resolved like so:

add_filter('the_content', 'do_shortcode', 11); // AFTER wpautop()

Executing do_shortcode instead when the the_posts hook runs should make sure they are executed early enough. the_posts runs immediately after posts are retrieved from the database. The following should work:

add_filter('the_posts', 'rutwick_shortcode_exec');

function rutwick_shortcode_exec($posts) {
    $post_count = count($posts);
    for ($i = 0; $i < $post_count; ++$i) {
        do_shortcode($posts[$i]->post_content);
    }
    return $posts;
}

It might be that lowering the priority will suffice:

add_filter('the_content', 'do_shortcode', 9);

Let it be noted, that I have not tested the above and I’m not guaranteeing nothing. Also, you might run into conflicts with wpautop, because if the above is applied, shortcodes (all shortcodes!) are now resolved before it filters the content.

EDIT: It might be safer to run your own replacement function that early (the following will assume your shortcode is called [next]):

function do_rutwick_shortcode($content) {
    $content = preg_replace('{\[next\]}','<!--nextpage-->',$content);
    return $content;
}

and call that using either one of the two above methods (i.e. hooking it into the_content with a lower priority number or replacing do_shortcode(...) with do_rutwick_shortcode(...) in the above for loop). If you choose to do that, using add_shortcode becomes superfluous. Also, if you opt for hooking into the_posts the preg_replace could be run directly in said function, two would not be needed, i.e.:

$posts[$i]->post_content =
    preg_replace('{\[next\]}','<!--nextpage-->',$posts[$i]->post_content);

would save you a function call.