Obviously requires a little reworking to Class::DBI (which could also greatly simplify the application code), but check out Class:DBI::Pager.

My other suggestion would be to just bring back all the rows to perl, but only access them through some custom "paging" methods. (basically recreating what the Class::DBI::Pager module does for you)