How to ensure a program is always running but without root access

You need to configure auditd to record execve events. Example on RHEL5:

[root@ditirlns01 ~]# auditctl -a always,entry -S execve
WARNING - 32/64 bit syscall mismatch, you should specify an arch
[root@ditirlns01 ~]#

I ignore the arch warning and it doesn't seem to matter but you can use -F arch=b64 or -F arch=b32 to set it if you want.

The result of the above is:

[root@ditirlns01 ~]# ls /tmp/whatever
ls: /tmp/whatever: No such file or directory
[root@ditirlns01 ~]# grep whatever /var/log/audit/audit.log
type=EXECVE msg=audit(1386797915.232:5527206): argc=3 a0="ls" a1="--color=tty" a2="/tmp/whatever"
type=EXECVE msg=audit(1386797927.133:5527241): argc=3 a0="grep" a1="whatever" a2="/var/log/audit/audit.log"
[root@ditirlns01 ~]#

That's obviously quick and dirty but that's the basics of how you do it. What you need to do exactly probably depends heavily on what you're trying to do exactly. You can reduce audit flow using various filters in the auditctl command but I don't know any of that information so I don't know what to include. If you need something more specific, I'd suggest you either check the man page or post a comment to this answer and I'll update it some more.

Hope that helps push you in the right direction.

EDIT:

Since your question involves looking at a particular user I can show you that:

[root@ditirlns01 ~]# auditctl -a always,entry -S execve -F euid=16777216
WARNING - 32/64 bit syscall mismatch, you should specify an arch

Identical to the above, but only execve's by someone running with the effective user ID of 16777216 will get logged. If you need to specify the user's loginuid value (who they initially logged into the system as) then you filter by auid instead:

[root@ditirlns01 ~]# auditctl -a always,entry -S execve -F auid=16777216
WARNING - 32/64 bit syscall mismatch, you should specify an arch

AUID/loginuid filters would be useful for example if the user will do a su or sudo to root. In that situation there will be a lot of stuff running as root, but you're only concerned with the stuff that got kicked off by the user in question. auditctl also lets you stack filters so you can filter by both euid and auid:

[root@ditirlns01 ~]# auditctl -a always,entry -S execve -F auid=16777216 -F euid=0
WARNING - 32/64 bit syscall mismatch, you should specify an arch
[root@ditirlns01 ~]# ls /tmp/nashly -ltar
ls: /tmp/nashly: No such file or directory
[root@ditirlns01 ~]# grep nashly /var/log/audit/audit.log
type=EXECVE msg=audit(1386798635.199:5529285): argc=4 a0="ls" a1="--color=tty" a2="/tmp/nashly" a3="-ltar"
type=EXECVE msg=audit(1386798646.048:5529286): argc=3 a0="grep" a1="nashly" a2="/var/log/audit/audit.log"

There are more than one way to accomplish this.

1. You can put your startup script in /etc/init.d and make it resemble to one of the existing scripts over there. But depending on your Linux comfort level, this may be a little daunting.

2. You can make this a service and make the service start at the boot time. Just do a google search on "how to make my program a service" and you will come across a lot of pages. More than what you can shake a stick at.

3. If your app is startin g with one single command and is not dependent on anything else, you can add the start-up command at the end of /etc/rc.local file.

You can also put it in the cron to execute at the startup but this is not the way it should be done, in my opinion