It depends what are you looking for: loading speed it's just an effect of network speed (which often is what you are looking for) and server side processing performance (hardware performance).
One factor to keep in mind is where the host is located: if your audience it's mostly in Europe, would be useful to get an host close to the main European backbone. Similarly for other Geographical locations.
After you have decided this, you could use stress-test tools like siege (on UNIX) to create lots of requests to a webpage and see how the host behaves under stress (using the tools you mentioned).
In the case of shared hosting and virtual server you can never be 100% sure that an host is going to be consistently fast (or slow), as your test might be influenced on other site's activity on the same host. It would be good to test during different times and for a relatively long period of time (for example one test every few hours for a week), in order to have a good "rough idea" of the host's speed.
To be fair, you should test the exact same site(s) and page(s) on every host (with the same frequency).