You could build a plugin to grab all the entries and then assign that new category to it that way.
This bit of code is untested but this should do it, since this is a one off thing, you can get away with just doing it in chunks by setting the limit and offset, otherwise I'd recommend creating this as a Task:
// get all the entries
$criteria = craft()->elements->getCriteria(ElementType::Entry);
$criteria->section = "news"; // just using news as an example, be sure to set the appropriate section handle
$criteria->limit = null;
// $criteria->offset = null; // you could use the limit and offset field to do this 200 at a time, to avoid it timing out on you
$criteria->status = null;
$entries = $criteria->find();
$categoryIds = array(222); // this would be the new category (its ID) that you want to assign to the entry, be sure to set the correct ID here
for($i=0; $i<count($entries); $i++)
{
$entry = $entries[$i]; // for easier reference
// lets get the existing categories that are assigned to this entry and add it to the new category ID you set a few lines above, if there are no existing categories for this, then you can remove this for loop entirely
for($c=0; $c<count($entry->categoryFieldHandle); $c++)
{
$categoryIds[] = $entry->categoryFieldHandle[$c]->id; // be sure to replace categoryFieldHandle with the category field handle for the category field
}
// setting the categories to this field, be sure to replace categoryFieldHandle here too
$entry->getContent()->setAttributes(array(
'categoryFieldHandle' => $categoryIds,
));
craft()->entries->saveEntry($entry); // save the entry
}