You are correct on your first point - if you don't create a LinkPost then the feed item doesn't get sent to embed.ly for processing and the embedded player doesn't appear.
You are also correct that you can specify either a group or a record id as the parent id.
If you are looking to have the post appear in both the the group feed and the record feed, your only option is to duplicate the post.
If, however, you can live with a link back to the parent record in the post, you can simply embed this into the feeditem.body field.
I've tweaked one of my existing pieces of code to a simple visualforce page and controller. The page allows the user to enter a URL for a youtube video, a link title, the group to post to and the id of an opportunity the post is also related to:
<apex:page controller="ChatterPostController">
<apex:form >
<apex:pageBlock >
<apex:pageBlockButtons >
<apex:commandButton value="Post" action="{!doPost}" />
</apex:pageBlockButtons>
<apex:pageBlockSection columns="1">
<apex:outputLabel value="Detail"/>
<apex:inputText value="{!detail}" />
<apex:outputLabel value="Link URL"/>
<apex:inputText value="{!linkUrl}" />
<apex:outputLabel value="Link Title"/>
<apex:inputText value="{!linkTitle}" />
<apex:outputLabel value="Opportunity ID"/>
<apex:inputText value="{!oppId}" />
<apex:outputLabel value="Group ID"/>
<apex:inputText value="{!groupId}" />
</apex:pageBlockSection>
</apex:pageBlock>
</apex:form>
</apex:page>
and the controller takes this information and creates a link post to the group, but also adds a link to the opportunity:
public with sharing class ChatterPostController {
public String detail {get; set;}
public String linkUrl {get; set;}
public String linkTitle {get; set;}
public Id oppId {get; set;}
public Id groupId {get;set;}
public PageReference doPost()
{
FeedItem fitem=new FeedItem();
fItem.parentId=groupId;
fItem.linkUrl=linkUrl;
fItem.title=linkTitle;
fItem.body=detail + ' Opportunity: ' + System.URL.getSalesforceBaseUrl().toExternalForm() + '/' + oppId;
insert fItem;
return null;
}
}
The resulting post in the group feed is as follows:

The opportunity URL looks slightly odd as it is derived from a visualforce page, but it is a clickable link and you do end up on the correct opportunity page. Unfortunately you can't turn this into an anchor tag and provide a friendly name.
In addition to the suggestions by BritishBoyinDC, an easier way would be by inserting the entries from the public site into a custom object. Then have a scheduled class pick up the messages from the custom object and post for chatter feed. This, however, would not be real-time. The scheduled job at best can run once every hour.
Best Answer
Currently, we can't do it in Salesforce Chatter feed. But we can create a custom Chatter site using rails with markdown syntax.