I'm in the middle of a similar issue (incidentally also on arch)
Grub is failing to find this file and run because it is using an incorrect "prefix" in my case.
Here is what you do. You boot into grub rescue mode, then you simply figure out how to make it boot.
First you run set this will list variables, for example mine is
Now, the prefix is the variable where grub looks for the normal.mod file. In my case hd1,msdos3 is the same as /dev/sdb3 (similarly, hd0,msdos1 would be /dev/sda1) what you may want to do to see a list of valid partitions is type in ls
Now, in my case, again, grub was installed on /dev/sdb1 which was mounted as /boot in my arch partition, so the correct prefix would be (hd1,msdos1)/grub
So for me to boot, I need to do this:
In your case you will have to either remember or guess which partition you installed grub on. You can guess wrong, it won't do any harm, the insmod command will simply fail and you can try again with another partition.
After this, grub loads as it normally should, and I can pick out of the list what I want to boot. Normally when a mess like this occurs, reinstalling grub to your mbr (using grub-install) should fix it permanently so you don't have to do this every time you boot. I however am having a lot of difficulty finding out what to do if fixing it isn't this easy (or I'd share what you should do).
Only if this fails (e.g. if the prefix is correct but you still can't boot) should you resort to live or rescue cds to work around the problem (it is best to avoid that)