Anti-Mage is a strong carry and Shadow Shaman a strong disabler/pusher. I assume the two of them are laning together, but if not the same will still somewhat apply. Trying to outcarry Anti-Mage usually isn't a very good prospect. If you're really determined to try to do that, Riki and Slardar are your best options.
Otherwise, you need to have someone strong to harass Anti-Mage when he's at his weakest and slow down his farm. If he's allowed to farm easily for 10-15 minutes he's incredibly harder to deal with in teamfights. You can't expect to kill him, however: blink is too good of an ability. Instead, you want someone who's not going to be threatened by him much in lane.
Shadow Shaman is not a very good babysitter because he needs early levels. His autoattack range, damage, and armor are all low, and so he is easily outclassed by an enemy harasser. Once Shadow Shaman is more subdued, you can turn to keeping the Anti-Mage from getting easy farm.
I recommend Lich or Venomancer for this purpose, but you'll need a lane partner with a stun as well to prevent Shadow Shaman from just gripping you. Anyone with a stun will do, but I'm not sure if the bots will be smart enough to use their stun as an interrupt. (At this point I should mention that you guys should be laning against each other if you're going 2v2 with 3 bots per team, otherwise you're just seeing who's better at taking advantage of dumb bots.) Other heroes like Shadow Demon, Obsidian Destroyer, and Bane can be useful counters to Anti-Mage at various stages of the game because of their spells, while heroes like Leshrac and Death Prophet can push towers and make it more difficult for Anti-Mage to farm.
Countering Rhasta (Shadow Shaman) is a lot more simple. You just need to be coordinated to quickly stop his Shackle, and don't be out of position enough to be Hexed. If you get ward-trapped, either use Phase Boots to walk out or kill one of the edge (not corner) wards and then walk free.
Ghost Scepter and Force Staff deserve special notice as great item pickups against both of these heroes. Shadow Shaman's wards won't be a threat and Anti-Mage can't stay on you (but be wary of his allowing his ultimate to do extra damage with Ghost Scepter). Force Staff also helps save teammates (Force Staff them away from the Anti-Mage, forcing him to commit more heavily for a kill attempt).
tl;dr: Lane Lich and a stunner against the AM. Get pushing power elsewhere. Deny him farm, use Frost Armor/Force Staff/Ghost Scepter in midgame to prevent him from killing people quickly with melee attacks. Push heavily during this time to earn a gold lead and hopefully take a set of Barracks quickly. You don't want to go lategame against an Anti-Mage without a similarly powerful carry like Riki/Slardar/Faceless Void.