Can I build a pergola on an existing deck, without digging more footers?
This is quickly going to become too complicated to tell you for sure if your deck will be able to support a structure like a pergola, but if it is even half the weight of your typical hot tub then your deck will very likely not support it.

To accurately determine this you need to figure out the additional #'s/sq ft of load that a structure as large as a pergola will place on top of the deck.  Doing this is simple with something like a spa where you have a clear square footage area and a relatively even weight  distribution when filled with water and people.  This is not so easy to determine with a structure where certain points of the structure are going to carry the weight of the structure differently.  The weight is not as evenly disbursed.

Right off the bat there I would advise you to consult an engineer with your structure plans to determine if this is feasible and safe.  This is completely disregarding the fact that your deck is only as strong as its weakest point.  If your house is brick and your ledger board is attached with carriage bolts then even if the joists were on 12" centers then you are still likely putting entirely too much stress on the ledger board.  You also could have a lot of problems if any part of your structure is going to sit over that 2' overhang.

In the end, an experienced engineer will probably be able to confirm pretty easily if this will be feasible or not.