Du har tyvärr inget annat val, om du inte kan förlänga slutartiden. Om du har de objektiv som framgår av din profil så har du ju i alla fall bildstabilisering, så vid f/4 borde du klara dig ganska bra. Är du stadig på handen så bör det funka att fota vid 1/20 eller så vid 100 mm brännvidd, med bildstabiliseringen påslagen.
Bruset kan bero på mängder av saker. Exempelvis vilken råkonverterare du använder, eller vilka JPG-inställningar du har i kameran om du inte använder råformat. Även vitbalans spelar in ordentligt. Vid ISO 1200-1600 bör du inte få något synbart brus med en 5D MkII i små visningsformat om du hanterat bilden på ett optimalt sätt (vilket inte är det lättaste).
Den där bilden är grymt underexponerad. Du hade kunnat höja uppåt två hela steg, ledigt. Inte för att det hade givit mindre brus (för då hade du tvingats höja ISO ännu mer), men det hade sett såpass mycket bättre ut att man inte tänkt på bruset.
Det framgår inte vilka slutartider du använder för dina bilder, sett till brännvidden på objektiven. Kanske det är där boven finns.
Tillägg: Nu ser jag att du fotat bilden vid 1/1000 och f/8. Där har du problemet. Det finns ingen anledning att ha så enormt kort slutartid med ett objektiv som har bildstabilisering. Du hade kunnat fota vid f/4, 1/100 sekund (eller längre) och lägsta ISO-tal och ändå fått högre exponering;-) Fin bild för övrigt