Um, no, not all of those queries will use your index. I'm sure if you run explain on all of those queries, you'll see this to be true. You should read this (see
http://dev.mysql.com/doc/refman/5.0/en/mysql-indexes.html) to learn how MySQL uses indexes.
The gist of it is that MySQL cannot use a partial index unless the columns you are searching form a leftmost prefix of the index. For example, your index consists of (col1, col2, col3, col4). This means that the index can be fully used if you search using the column combinations (col1), or (col1, col2), or (col1, col2, col3) or (col1, col2, col3, col4). The index is only partially used on queries that search (col1, col3), or (col1, col4), or similar.
So for your queries, query #1 can take full advantage of the index. Queries #2 and #3 cannot use the index at all because the columns you search do not form a leftmost prefix of the index. Query #4 can use the index to search for the col1 value, but not col3 (it must data scan for col3). Query #5 can use the index to search for the (col1, col2) values, but not col4.
As for the speed of your count(*) statement, I can't explain that without knowing more details of your system and database schema. A lot of things could be coming into play. Count queries are faster if you are using the MyISAM engine than one of the other engines.
-Dave