How to decrease memory usage in codeeval Road Trip challenge
I don't think it's a good idea to preprocess the line so much.  line = line.strip() duplicates the line, for no benefit.  I don't know why if line == "": continue should be needed.  line = line.replace(';', ' ').replace(',', ' ').split() degrades the data, and takes two passes to do it.

Here's how I would read the input:

for line in fileinput.input():
    route = itertools.chain([0], sorted(
        int(city.group(1)) for city in re.finditer(r'[A-Za-z]+,(\d+);', line)
    ))


Using fileinput.input() will let you take input from either a file specified on the command line, or sys.stdin if no file is specified.  re.finditer() will look for the pattern and capture the numbers that you need.

In Python 2, you should use xrange() instead of range().  However, if you capture just the numbers, as I've done above, then you wouldn't need to use range() or xrange() to extract every other item.

Each of your list comprehensions results in another temporary copy of the data.  result.insert(0, distances[0]) is also bad for performance, since every entry must be copied to make room for one entry at the front of the list.

To finish off the solution, I would do this:

print(','.join(str(b - a) for a, b in pairwise(route)))


… using the pairwise() recipe from itertools.