Word-Ladder solver in Python 3
I'm a little bit short on time at the moment, but I'ld like to share a few minor observations with you. Maybe I will also find time to look at performance related optimizations and expand it later.



You said you would like your code to be Pythonic. With that in mind you could replace print(list(reversed(values))) by print(values[::-1]) which uses slicing (nice explanation on Stack Overflow) to revert the list. Since you need the complete list nevertheless, there is no real advantage in using a reverse iterator instead of a list directly.

Also since "Explicit is better than implicit." (from Zen of Python) I would prefer to see 

distance = hamming if input_mode == 1 else levenshtein


or something similar instead of

distance = [hamming, levenshtein][input_mode - 1]


The proposed version would also allow you to drop the string to int conversion. It would even work if the user entered something else than the two values presented by the prompt. levenshtein would be assumed to be the default then. Change the if to your liking if you prefer hamming as default. Although this might not be something to think about, since you have an input validation in place (good). However, the way it is written could be improved since you have a really small range (read: two) values that are valid. That makes it possible to list them explicitly:

# Validate user input
if input_mode not in (1, 2):
    raise ValueError("Invalid mode: " + input_mode) 


This almost reads like normal language.