You could just put each MP4 into a file and go to right click - > Properties - > Customize - > Change Icon.
Or, you can change the MP4 icon by going to:
Start -> regedit.exe -> HKEY_CURRENT_USER -> Software -> Microsoft -> Windows -> CurrentVersion -> Explorer -> FileExts -> .mp4 -> UserChoice
Then look at the value next to "Progid" and underneath "Data". For instance, mine would say gomplayer.mp4.
Then go to HKEY_CLASSES_ROOT and search for your specific file name that we just found. Once you find it, open up DefaultIcon. If there is no folder called DefaultIcon, you can right click on the folder and go to New -> Key. Name it DefaultIcon.
Once inside the DefaultIcon folder, you can then edit the value next to (Default) and underneath Data. Change the directory to your image file. For instance, if I had a folder on my desktop named MyFolder, with an image file such as MyIco.ico inside, the directory would be:
C:\Users\Taylerzy\Desktop\MyFolder\MyIco.ico, 1
The one at the end tells which icon number we are referring to (alphabetically).
Edit:
In regards to using a program to make this change, you could use
Default Programs Editor, which will allow you to edit the icon by running the exe, going to file type settings, icon, type in mp4 in the search box, double click the value, browse for your icon, and click save to registry. This essentially does the same thing, only it's a little easier if you don't want to edit the registry yourself.