SQLite count performance

I'm experiencing (in my opinion) weird performance issues when trying to find the total number of records in a table. The (boiled down) table looks like this:

CREATE TABLE "records" (
    pk INTEGER PRIMARY KEY AUTOINCREMENT,
    other_table_fk INTEGER,
    int_value INTEGER,
    FOREIGN KEY(other_table_fk) REFERENCES other_table(pk)
    ON DELETE CASCADE
}

CREATE INDEX int_value_idx ON records(int_value);

Now when I try to query the count of all records this takes a long time:

$ time sqlite3 db.sqlite "SELECT count(ROWID) FROM records"
100000

real    0m2.962s
user    0m0.162s
sys     0m2.618s

When the indexed field is used the query is way faster (but the count is the same):

$ time sqlite3 db.sqlite "SELECT count(ROWID) FROM records WHERE records.int_value > 0"
100000

real    0m0.083s
user    0m0.015s
sys     0m0.057s

My problem is, that the table schema is dependant on the users configuration, so I cannot be certain that I have an indexed field in the table, but I still want to have the performance of the indexed COUNT.

I know that primary keys have an index on their own, but in this case this does not seem to help:

$ time sqlite3 db.sqlite "SELECT count(ROWID) FROM records WHERE records.pk > 0"
100000

real    0m2.965s
user    0m0.138s
sys     0m2.636s

Weirdly, even if I create an additional index on the primary key, this does not help either:

$ time sqlite3 db.sqlite "CREATE INDEX records_pk_idx ON records(pk)"

real    0m3.288s
user    0m0.313s
sys     0m2.812s


$ time sqlite3 db.sqlite "SELECT count(ROWID) FROM records WHERE records.pk > 0"
100000

real    0m2.974s
user    0m0.154s
sys     0m2.624s

I read suggestions to circumvent this issue, either by using MAX(_ROWID_) (not an option, as I do regular deletes) and using triggers to store the number of records (seems "dirty" to me to store redundant information).

Are there any other ways to speed up this seemingly trivial queries?

For the record:

$ sqlite3 -version
3.6.20

I'm stuck with this version.