I found that my script cannot be on the /sdcard if I want it to be marked as "executable".

So I stuck it into /sbin instead:
su
mount -oremount,rw /
cp my.script /sbin/
chmod 0755 /sbin/my.script
mount -oremount,ro /
exit