Restrictions around promoting a pawn
No, a Pawn must be promoted to a Knight, Bishop, Rook, or Queen.
Yes, pawn promotion isn't limited to captured pieces.
My guess is that normal people don't carry around multiple sets of pieces, probably only tournaments. Most likely tournaments keep far more queens around than other pieces since promotion is usually to a queen (99% of the time).
The Wikipedia page says this (emphasis mine):

Promotion is a chess rule describing the transformation of a pawn that reaches its eighth rank into the player's choice of a queen, knight, rook, or bishop of the same color (Just &amp; Burg 2003:16). The new piece replaces the pawn on the same square and is part of the move. Promotion is not limited to pieces that have already been captured (Schiller 2003:18–19). Every pawn that reaches its eighth rank must be promoted.

If you want a copy of the USCF's Rulebook: The Official Rules of Chess, 5th Edition (2003) that they are referencing though, it will cost you.
The FIDE has this in their rule book.

3.7e. When a pawn reaches the rank furthest from its starting position it must be exchanged as part of the same move on the same square for a new queen, rook, bishop or knight of the same colour. The player’s choice is not restricted to pieces that have been captured previously. This exchange of a pawn for another piece is called ‘promotion’ and the effect of the new piece is immediate.
6.12 b. A player may stop the clocks only in order to seek the arbiter’s assistance, for
example when promotion has taken place and the piece required is not available.