In Maple 15 I'm getting times of about 12 seconds on decent, fairly recent hardware. I used
with( LinearAlgebra ):
N := 10^4:
A := RandomMatrix( N, N, 'generator' = 0 .. 1, 'density' = evalf( 1 / N ) ):
time( Modular:-CharacteristicPolynomial( 2, A, t ) );
for testing. The fact that it is sparse is important. Runtimes for dense examples were much, much longer.
EDIT: It seems that if you use a sparse matrix data structure, and smaller (one byte) integers, this can be done much more efficiently. If you have access to Maple 14 or 15, try this (and note that, here, $N = 10^5$):
with( LinearAlgebra ):
N := 10^5:
A := RandomMatrix( N, N, 'generator' = 0 .. 1, 'density' = evalf( 1 / N ), 'storage' = 'sparse', 'datatype' = 'integer'[1] ):
time( CharacteristicPolynomial( A, t ) mod 2 );
On my machine, I get the answer in less then 0.5 seconds. (It took longer - about 0.75 seconds - to construct the matrix!) Memory used was about 45.3 Mb, but going back to size $10^4\times 10^4$ reduces the memory to 2.7 Mb. I did examples with $N = 10^6$ in about 5 seconds and 220 Mb of memory.
Anyway, it's clear from the various answers that there are computer algebra systems out there that can handle the computations you are interested in (at least Maple and Fermat, and likely others), so you should be in a position to choose whichever system is most convenient for you.