Originally Posted by Frostmourne
I tried unassociating the extension file using cmd prompts assoc .mp4=
followed by ftype WMP11=
but those didn't work for me.
I went back to the "unassoc_1_4.zip" utility that I downloaded from An Utility to Unassociate File Types in Windows 7 and Vista
and clicked "Delete file type" button (I think this deletes file extension from the registry) since the "Remove file Association (User)" button was grayed out. This works! The .mp4 files are no longer associated to Windows Media Player and the WMP icon is also removed. Now when I click on any .mp4 file, Windows asks me to choose a program to open with. This is exactly with I wanted!
Thanks everyone for your suggestions!