How do I customize my WordPress shortlink structure in link-template.php without a plugin?

Okay, so, as mentioned in my comment to you: altering core files is not a good idea. But here is a plugin solution.

First we’re going to create our own rewrite rules that rewrite s/123 (replace 123 with a post ID) to index.php?short=123. We’ll also have to filter the WordPress query variables so we can use them later.

<?php
add_action( 'init', 'wpse26869_add_rewrites' );
function wpse26869_add_rewrites()
{
    add_rewrite_rule( '^s/(\d+)$', 'index.php?short=$matches[1]', 'top' );
}

add_filter( 'query_vars', 'wpse26869_query_vars', 10, 1 );
function wpse26869_query_vars( $vars )
{
    $vars[] = 'short';
    return $vars;
}

The add_rewrite_rule call says “rewite s followed by a slash and a string of one or more digits to index.php?short=the_string_of_digits.

Then we can hook into template redirect and see if our query variable is there. If it is, we’ll try and get a permalink out of it. If that fails, we’ll throw a 404 error. Otherwise, we’ll use `wp_redirect’ to send folks to the actual post.

<?php
add_action( 'template_redirect', 'wpse26869_shortlink_redirect' );
function wpse26869_shortlink_redirect()
{
    // bail if this isn't a short link
    if( ! get_query_var( 'short' ) ) return;
    global $wp_query;

    $id = absint( get_query_var( 'short' ) );
    if( ! $id )
    {
        $wp_query->is_404 = true;
        return;
    }

    $link = get_permalink( $id );
    if( ! $link )
    {
        $wp_query->is_404 = true;
        return;
    }

    wp_redirect( esc_url( $link ), 301 );
    exit();
}

Finally, we hook into get_shortlink to change how our rel=”shortlink” appears in the <head> section of the site, and elsewhere. This new shortlink structure will reflect the rewrite rule we wrote above.

<?php
add_filter( 'get_shortlink', 'wpse26869_get_shortlink', 10, 3 );
function wpse26869_get_shortlink( $link, $id, $context )
{
    if( 'query' == $context && is_single() )
    {
        $id = get_queried_object_id();
    }
    return home_url( 's/' . $id );
}

As a plugin:
https://gist.github.com/1179555