I do have prepared theme files (with __(), and _e(), etc), but they lack domain argument. There are lots of such string scattered around the theme files, editing by hand seems to be a dreadful perspective. Is there any tool to do this quickly? I remember there was a script somewhere, but I can't find it now.
There's no perfect solution, because your search would be pretty general. Keyboardshortcuts are a real help in such cases. Ex. Notepad++ [Ctrl] + [F] = search. Then [N] for find and [R] for replace.
Most editors offer search (that includes search&replace) across files (ex. notepad++). You could do a search for
__(', take a look at the search results list (opens at the exact position with a double click) and then replace
', MY_TEXTDOMAIN );
Note: Top of your functions.php should then have something like:
define( 'MY_TEXTDOMAIN', 'my_textdomain_string' );
This will hold you away from replaceing everything again, when you decide to change the textdomain string, because it's stored centrally in the Constant MY_TEXTDOMAIN.