Found a solution for this.
Set up the tox.ini as follows:
[testenv]
setenv=LIBRARY_PATH=/usr/local/lib
CPATH=/usr/local/include
deps=pysqlite
This will set the library_path and CPATH before tox sets up the virtualenv dependencies using pip. Everything runs smoothly afterwards.
Note: This requires tox 0.9 or better