Você já tentou várias soluções, então não sei exatamente se isso é novidade para você ou não. De qualquer forma, enfrentei um problema semelhante com o mesmo código de erro exato. Minhas anotações da época dizem que resolvi esse problema instalando a versão do desenvolvedor da biblioteca, libsqlite3-dev .
Com o tempo, descobri que essa é uma boa regra empírica: quando algo falha, e você acha que tem todos os pacotes relevantes, a falha se deve à falta do pacote de biblioteca -dev .
Se isso não for suficiente, que tal executar um strace ? Talvez isso possa adicionar algumas informações úteis.