The app is live on the Windows Store and has a 8.0 version. If I re-target to Windows Phone 8.1 and publish with new features, will it be available for Windows Phone 8.0 users?
Most of our users are still on 8.0.
The user (OS/Store) downloads the most suitable package of the app. If user has WP8.1 and your app has a 8.1 package, then this will be installed, otherwise 8.0 app package will be downloaded.
From what you have written, you already have a working WP8.0 version of the app, now if you want to add some new features from 8.1 then, once you retarget the app, you have to add new package to your app when you are updating it. Do not replace the old working 8.0 package. Once you have added new package and it has passed certification, all users that have 8.0 version of your app and 8.1 OS version, will be prompted that there is an update available.
What is important:
I've done similar thing with WP8.0 -> WP8.1 Runtime, I also recommend to test it on beta app, so you will be sure how it works.
If you re-target the app to Windows Phone 8.1, it'll be available to only Windows Phone 8.1 users. If you submit such an app to Store, it'll be displayed only in devices running Windows Phone 8.1.
However, you can submit two packages for same app in Windows Phone Store. So while submitting an update for your app, instead of replacing the existing Windows Phone 8.0 package, you can add another package for the Windows Phone 8.1 version which will have new features. The Windows Phone Store will ensure that it shows the correct XAP to correct OS version. This way, Windows Phone 8.1 users will be able take advantage of the new features, while Windows Phone 8.0 users will still be able to access the old app.
Going forward, if you want to support both OS versions, I'll suggest to keep a copy of Windows Phone 8.0 project before re-targeting to Windows Phone 8.1.