If you have not already used a base template with presentation, this will be tricky. Normally I would have a base page template with some core presentation elements and then all other page templates would inherit from that - also I try to have very few page templates.
For your problem you are probably going to have to add the element to the standard values on your page templates.
You could script this with Sitecore PowerShell Extensions using something similar to this:
$item = get-item master:\content\Demo\Int\Home
$device =Get-Device -Default
$contentDataSource = get-item master:\content\Demo\Int\Home\about-us\employee-stories\adam-najmanowicz
$ImageDataSource = get-item master:\content\Demo\Int\Data\Images\d56cf7e777a2496aa6489a7bffc03539
$rendering = get-item master:\layout\Sublayouts\ZenGarden\Basic\Content
Add-Rendering -Item $item -Device $device -Rendering $rendering -Placeholder main -Parameter @{FieldName ="Title"} -DataSource $contentDataSource
$rendering = get-item master:\layout\Sublayouts\ZenGarden\Basic\Image
Add-Rendering -Item $item -Device $device -Rendering $rendering -Placeholder main -DataSource $ImageDataSource
$rendering = get-item master:\layout\Sublayouts\ZenGarden\Basic\Subtitle
Add-Rendering -Item $item -Device $device -Rendering $rendering -Placeholder main -DataSource $contentDataSource
$rendering = get-item master:\layout\Sublayouts\ZenGarden\Basic\Title
Add-Rendering -Item $item -Device $device -Rendering $rendering -Placeholder main
Source: Adam Najmanowicz Gist.
This should serve as a good starting point. Here is the documentation of the Add-Rendering function:
https://sitecorepowershell.gitbooks.io/sitecore-powershell-extensions/content/appendix/commands/Add-Rendering.html
Credit to @pascal-mathys for this answer on this question