How do you choose your new product name, and put yourself at safe side?

We want to use a name for our upcoming product.

That's fairly common :) :)

determine whether we can use a name for our next product name, legally

/// I'm not a lawyer and if i talk shit i shall not be held liable ///

The criteria to establish US trademark rights is "use in interstate commerce". If the app that has the same name you want to use has sold even one copy, then they have gotten the trademark rights for the name.

However, US trademark law also has "use it or lose it" rule, which means that if the other app has not used its trademark for long time, then they have lost the right to the name, and you are free to use it.

Also note that strictly speaking it's not "illegal" to use name that is somebody else's trademark. The owner of the trademark (not the government) is responsible for protecting its trademark, and normal trademark violations are not criminal offenses.

So, effectively you can use any name you want, and hope that you won't get a Cease and Desist letter requiring you to change name. If the other app is out of business, the risk is low.

how can we register as the "legal owner" of the name, in cost effective way

Closest thing is to register your trademark.

I self-filed US federal trademark registration online, without lawyer, and it was accepted just fine. See USPTO for details.