You can do this by using DOM level2 CSS interfaces:
var sheet = window.document.styleSheets[0];
sheet.insertRule('strong { color: red; }', sheet.cssRules.length);
On all but IE8 and prior, which uses its own marginally-different wording:
sheet.addRule('strong', 'color: red;', -1);
There is also a theoretical advantage using this when compared to the createElement-set-innerHTML method, in that you don’t have to worry about putting special HTML characters in the innerHTML, but in practice style elements are CDATA in legacy HTML, and ‘<’ and ‘&’ are rarely used in stylesheets anyway.
You need a stylesheet in place before you can start appending to it like this. That can be any existing active style sheet: external, embedded, or empty, it doesn’t matter. If there isn’t one, the only standard way to create it at the moment is with createElement.