You could develop your own metabox for the page (with custom styling, probably) that allows selection of the template. I don’t know that generating screenshots is feasible, but you could definitely have it pull from some sort of associated file (eg: template name is template-name.php, screenshot is template-name.png).
With the replacement selection method generated, you can then just use remove_meta_box() to remove the default input box (see: Get List of Registered Meta Boxes and Removing Them) and you should be set!