Is there a way to sign message on front-end and then send signature to backend which will call a transaction in a contract

This is functionality of wallet in fact.

we are trying to make gas free transactions and pay for user

so we need user to just sign message in wallet, it's will return signature to us, then we will send it to backend and backend will send this to contract, then the contract will check the signature if it is correct user

I am busy with writing a new article that makes this topics more clear .its link : https://github.com/ton-society/grants-and-bounties/issues/20

Short answer is : Although conventional user wallet have deterministic way of paying gas , but as TVM is complete turing machine , the possibility is endless .you can develop any algorithm you need without any doubt.for special your usecase my suggestion is utilizing sharding as discuss in sharding article in ton blog . it means you need an infrastructure that your user has a special wallet with your specific requirement .

How is sharding even related to that?!!

Do they need to access user's NFTs/jettons?

https://blog.ton.org/how-to-shard-your-ton-smart-contract-and-why-studying-the-anatomy-of-tons-jettons

You've missed the point @bulbadubz makes. He needs service to pay for the entire message (so user can have *zero* balance), not just more optimal contracts architecture.

found out about "external messages" guess it's what i need

I sincerely admire your experience and knowledge. We will have a deep discussion soon .it seems you play with words.I am not pleased with your comment. Sorry for lack of time right now.

Currently, you cant pay gas for user. Wallet v5 has support for it
https://github.com/tonkeeper/w5