I'm looking for the fastest algorithm/package i could use to compute the null space of an extremely large (millions of elements, and not necessarily square) matrix. Any language would be alright, preferably something in Python/C/C++/Java. Your help would be greatly appreciated!
The manner to avoid trashing CPU caches greatly depends on how the matrix is stored/loaded/transmitted, a point that you did not address.
There are a few generic recommendations:

divide the problem into worker threads addressing contiguous rows per threads
increment pointers (in C) to traverse rows and keep the count on a per-thread basis
consolidate the per-thread results at the end of all worker threads.

If your matrix cells are made of bits (instead of bytes, ints, or arrays) then you can read words (either 4-byte or 8-byte on 32-bit/64-bit platforms) to speedup the count.
There are too many questions left unanswered in the problem description to give you any further guidance.
Computing the null space of a large matrix