Any nurse can do that also in Portugal. Going to a "centro de saúde" (health center) is a good choice. These are part of the national health system. In principle you don't need an appointment. Just go there and explain the reason. That is so fast and simple that they may solve it immediately. Be prepared and take some "patience" with you though. The system usually works well but you can always get some "old school" public servant. Being a foreigner you will most likely be very well treated. Portuguese in general are very pleasant, and like foreign visitors, but be prepared for that 0.1% chance. You might need to wait or return another day if it's crowded. It's hard to tell since that varies a lot in geographical area and time of the year.
In any case you can always call first to http://www.saude24.pt/ (808 24 24 24). This is a phone line from the national helth system to give advice about daily health problems (not urgency, that is 112). They will be able to help, and I would probably do this first. They can even point you to the nearest "centro de saúde"
There are also many private nurses /offices. It shouldn't be hard to find one. And a simple treatment/thing should be very cheap.
You can look in yellow pages for nurses: http://www.pai.pt/q/business/advanced/what/enfermeiros/?contentErrorLinkEnabled=true
You can also ask in a pharmacy where you can do it. There are many and often offer more services than just selling drugs (they often have specialized personnel) . They might actually remove stitches or point you in the right direction. I would definitely visit one to know.
If they're not too busy I wouldn't be surprised that they helped you, even if they don't offer the service by default. And without any promise, I wouldn't even be surprised if they didn't charge for such a thing.