You can just store a flag in the keychain. The contents of the keychain are preserved across app reinstalls.
To get the first installation time of your app, check when the first time the app binary has been written to disk:
if (flag_in_keychain_not_present()) {
// installed for the first time
set_flag_in_keychain();
struct stat st;
stat([NSBundle mainBundle].executablePath.UTF8String, &st);
time_t installed = st.st_mtime;
}