You basically have already described the solution, and there's not much else.
Either the user's data must be in user's own directory; usually, the right place for the database and ini files is user's %appdata%, this is the recommended practice;
or in order to install anything to the location that affects the whole machine, such as %programfiles% or "all users" profile, naturally, the user must be an administrator. There's no way around this, and if there was, it would be security breach.
One way standard user can install an application requiring admin rights is when the application is assigned to the machine in group policy by the network administrator - in which case it is in fact installed by the administrator's order, so Installer goes into elevated mode.
See
http://msdn.microsoft.com/en-us/library/aa369519(VS.85).aspx for more details.