The exact error when executing the cron job manually (/usr/bin/php -f /var/www/vhosts/example.com/httpdocs/cron.php) was:
PHP Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 7 bytes) in /var/www/vhosts/onlinediscountmarkt.de/httpdocs/lib/Zend/Db/Statement/Pdo.php on line 290
This error can happen if Magento's cron_schedule table has too many records, coming from the log entries of past cron runs. So, delete all the entries, directly in the database with
TRUNCATE TABLE cron_schedule; or using phpMyAdmin or similar.
Now, when calling the cron job again from the command line, it finishes normally, without a crash.
It seems that the table could become that full because in "System -> Configuration -> System -> Cron", "History cleanup every" was set to "1440", thinking this was to be set in minutes. But instead, it seems it's set in days. The same for "Success history lifetime" and "Failure history lifetime" there. So better set all three to some meaningful value like "30".
This "Allowed memory size exhausted" error also persisted after installing the AOE Scheduler module and removing all scheduled cron tasks, then calling the cron job manually. This hinted to the fact that this error is unrelated to any single of Magento's various cron tasks (so also independent of installed contrib modules), and instead happens in Magento core. (This is Magento 126.96.36.199 by the way.)
Also, from searching the error message on the Internet, it appears that the "Allowed memory size exhausted" problem at this specific code location is a rather generic error that else happens for example when processing too many product records at once (see for example here or here).
This had me look at Magento's cron_schedule table, in this case it had 673498 entries according to AOE scheduler (in the database, even 830,881 rows). These were too many records for Pdo.php to process within the memory limits: in line with other reports of the "Allowed memory size exhaused" error in Pdo.php line 290, the error was here caused by too many records in this cron_schedule table.