Is there a way a cancel a stuck transaction without having a pay a gay fee?
Or does any successful transaction, except the ones sent from the same account with the same nonce, requires paying gas fees?
No. When you signed it, anyone (from the miners) can take it and process. With putting your signature you have made your authorization to execute the transaction. In general you have to raise gas price (10% or 15%) on transaction with the same nonce to resubmit.