I believe all you need to do is move your army away from the city and then approach the faction with a diplomat. I'm not 100% sure, but I don't think they'll accept the city if your army is near it.

I've had some problems when trying to give cities away. It seems that no faction will accept more than 2 cities as gifts from me; after that they stop accepting them. They always reply "We have nothing suitable to offer in return" - even though I'm trying to give it to them as a gift. I've tried everything, even asking for a small amount of mnai in exchange, but they still refuse to accept.

I tend to go a little mad with power and want to force these factions to develop how I see fit - but they make things difficult sometimes. That's when I roll out the legions and crush them, then give the city to another faction who is willing to take it.