You don't need live plants to cycle, no. They do help the process a bit though.
Just a regular water change to clean up the water-I imagine it must be pretty funky with all the old shrimp and whatnot. Don't do 100% change, though, or you'll risk losing the cycle.
Testing kits should be available at any pet store. The API liquid kit is quite good, though it's a bit expensive. It looks like this