Ever the conservative one, I would go for (2), with (1) being the second choice:

As you put it nicely: we can't have backward incompatible changes. If nobody has complained so far (has anybody complained? I don't see anythink on rt.cpan.org) it probably means that it is not really a problem for users.

I see an other option BTW: (4) (possibly optionaly), internally do a SELECT count(<query>) FROM... to get the info first, then do the query (all nicely wrapped in a transaction I would assume).

Maybe contacting the author of SQLite to get a function that would return the count, before using sqlite_step might also be a good idea, as it would move the extra step out of Perl (and out of your module) and into the core library.