Is it possible to start a program normally, and then later give it root or some other level of permission without restarting it?
No. In general, a program can only reduce its privileges (although there are ways for root owned programs to temporarily drop privileges and regain them).
The current best practice for such programs is to separate the privileged and non-privileged portions into separate processes, and have the non-privileged process invoke the privileged one as needed (e.g. this is how the clock indicator's preferences panel lets you change the system time, or how the terminal updates the list of logged in users).
This needs to be part of the program's design though: if a program is not designed to act this way, then you'll need to run it under
Yes. The software has to request it specifically though. PolicyKit is probably the best way.
Setuid also allows changing of privilege, but it's not a start as normal then go to root thing as much as a start as a service/drop/regain type of thing.