I have been experimenting with Fermat to see how this goes. For a 5000x5000 test case I made up, it computed the minimal polynomial (Wiedemann algorithm) in about 30 seconds, then using that, the characteristic poly in about 22 minutes. It used about 45 meg of RAM. This is on a three year old IMac.
I am the author of Fermat. You can find my email online, and the Fermat web site.
To the Maple person, James:
I tried your code in Maple and the kernel crashed, memory allocation failed. (My IMac has 4 gig RAM.)
Does your example really have only 1 entry per row? The test case I quote above with Fermat has about two per row. With one per row, I get the answer in 0.92 seconds.