Pawn wouldn't be stalemate because it can be promoted to a queen.

I think it's also possible to checkmate with a rook + king (if you corner the king and have your king cover the escape route from check).

Yup, you're right! The algorithm works like this: (each "move" is an implicit "continue" in the pseudocode)

    while no checkmate:
        If your rook is about to be taken, move it to the other end of the current rank.
        If the enemy king is on rank n and your rook is anywhere but rank n-1, move your rook to rank n-1 (unless it can then be taken, in which case move it to the end of its current rank.)
        If your king is anywhere but rank n-2, move towards there.
        If your kings are on the same file, advance the rook to rank n (unless it can be taken...)
        If |file of your king - file of opponents king| is odd, make a wasted move with the rook (keeping it on the same rank).
        If you've gotten this far, move your king towards the opponent's king (staying on the same rank n-2).

Rook + king is a simple checkmate (http://www.chesscorner.com/tutorial/basic/r_k_mate/r_k_mate....)

You can easily checkmate with a king and a rook, it just has to be along an edge of the board.

In rare circumstances you can checkmate with a king and a single bishop: http://www.chess.com/forum/view/more-puzzles/mate-with-one-b...

Any piece (well, except the king) can checkmate with cooperation from the opponent's pieces. The standard sets (queen, rook, two bishops, bishop and knight) are those with which you can force a checkmate against an opponent who just has a king.

Stalemate is a very specific term that means that the side to move has no legal moves. If checkmate is impossible this is generally called a "draw by insufficient material".