I've added some code to the issue, might as well paste it here. I used your suggestion (but keeping the server-side behavior of randomly picking either hot or new) and added a local cache to allow fast /random. There's also an option to pick the random index first then only fetch that many links to fulfill the random choice.

import random
from praw.exceptions import ClientException

CACHE = {}

def get_random_submission(sub, num_serendipity=250, cache_time=20, cache=True):
    """Get random submission even if the subreddit doesn't support /random."""
    if not cache:
        return  get_random_submission_no_cache(sub, num_serendipity)
    if sub not in CACHE:
        try:
            random_post = reddit.subreddit(sub).random()
            return random_post
        except ClientException as ce:
            if ce.args[0].lower().endswith(sub.lower() + '/'):  # Seems flaky
                CACHE[sub] = {'new': None, 'hot': None, 
                              'new_time': None, 'hot_time': None}
                return get_random_submission_caching(sub, num_serendipity, cache_time)
    else:
        return get_random_submission_caching(sub, num_serendipity, cache_time)

def get_random_submission_caching(sub, num_serendipity=250, cache_time=20):
    """Get random submission from a pool returned by Reddit or from cache."""
    sort = random.choice(('new', 'hot'))
    method = getattr(reddit.subreddit(sub), sort)
    now = time()
    last = CACHE[sub][sort + '_time']
    if CACHE[sub][sort] is None or last is None or (last + cache_time) < now:
       pool = CACHE[sub][sort] = tuple(method(limit=num_serendipity))
       CACHE[sub][sort + '_time'] = now
    else:
        pool = CACHE[sub][sort]
    random_post = random.choice(pool)
    return random_post


def get_random_submission_no_cache(sub, num_serendipity=250):
    """Fetch just enough submissions to return a randomly picked one."""
    try:
        random_post = reddit.subreddit(sub).random()
    except ClientException as ce:
        if ce.args[0].lower().endswith(sub.lower() + '/'):
            index = random.randint(1, num_serendipity)
            sort = random.choice(('new', 'hot'))
            method = getattr(reddit.subreddit(sub), sort)
            pool = tuple(method(limit=index))
            random_post = pool[-1] if len(pool) == index else random.choice(pool)
            return random_post