In the same way that they make tomato tortillas, is it possible to create french fries with a homemade recipe that is made from potatoes and tomatoes both? My idea is to create something that does not require catsup.
After cooking 90% of the way, pat fries dry on paper towels and lightly brush with a mix of ingredients--tomato paste, honey, vinegar, garlic/onion powder, and salt. Finish in the oven on very high heat (450-500) until the outsides begin to brown.
If you can only use tomatoes and not paste, reduce the above ingredients in a saucepan, substituting fresh tomatoes for tomato paste. Reduce to about 1/3 volume, so that it's closer to a sauce/glaze, and use that as a coating instead.
I can think of two approaches. In either case, you are going to want to use dehydrated tomato powder (or ketchup powder), as you certainly don't want to add the water content of the tomato to your fry. Option one would be to mix the tomato powder into a mashed potato, structure that with some hydrocolloid, and fry. The other, much simpler and probably better approach would be to season with a powdered-tomato spice mix immediately after frying.
You can fry tomatoes, but you will need to batter or bread them first. Googling for
deep fried tomatoes turned up a recipe that called for bread crumbs, it may be possible to substitute instant mashed potato flakes. Or you could fry the tomato and potato wedges and serve them together. You can also batter potatoes before frying, add some tomato paste or powder to the batter.
If your only goal is to create a no-catsup-required food, how about french frying carrots or sweet potatoes? Those fries tend to have more flavor than potato fries.