1) Can someone embed a separate free-standing program or separate tool inside of a typical video game that would be downloaded on-line simultaneously to the game installation?
It's possible to "embed" software to appear as though it's not getting installed along with the primary package, but it's sneaky and wrong.
It's also possible to request that users install additional programs in addition to the one they're currently installing. This isn't "embedding" per se, but rather is a request for the user to install an additional program.
The mechanism for requesting this differs by platform. On non-AppStore-like environments, the two software companies can make a deal where one agrees to include the other's installer along with their own.
In a modern consumer computing environment (such as the AppStore for Mac and iOS and the new Marketplace in Windows 8) this kind of application behavior won't get approved. You need to present some sort of request to the user indicating that you'd like them to download this other piece of software.
The "request" part is important. The AppStore and Windows Marketplace are enforcing this because installing software without a user's permission is a characteristic of malware. It's like somebody bringing an uninvited guest into your home without your consent. Sure, there's enough people doing it where it's not uncommon, but we all find that guy to be really irritating.
2) If so, is this a common practice and could you give me any examples of these?
This isn't as common as it once was. Commonly you would get the Yahoo Toolbar or the Gator Toolbar bundled with an application that you wanted to install. These programs typically sucked up a lot of resources, or introduced vulnerabilities that compromised the security of user's computers.
If the software you are requesting the user to install has a valid reason for being there, and you are up front about why you want it installed, users may check out the software out of curiosity. Honesty is key.
Download any games by Zynga or Atari or EA and similarly large companies on a mobile device. They will frequently show you popups asking you to download other software.
Pulling up Qqwy's comment into the answer because it's important for Travis to readr:
Important to note: There are still many programs that include other optional programs in their installer. Indeed these are not 'hidden', but because the users will need to úncheck the checkmark, many people still end up with installing the google toobar, yahoo toolbar, etc. even tough they don't really want it.