Learn Spanish (Spain): Tenemos el mismo coche.

In Spanish, most adjectives go after the noun (like coche rojo for red car). However, some adjectives like mismo (same) almost always go before the noun to show identity or quantity rather than a physical description.

Would mismo change if we were talking about a feminine word, like a bicycle?

Yes, mismo has to match the gender and number of the noun it describes. Since coche is masculine and singular, we use el mismo coche. If you were talking about a bicycle (bicicleta), you would say la misma bicicleta.

Why isn't the word nosotros (we) in this sentence?

In Spanish, the ending of the verb usually tells you who is doing the action. The -emos ending in tenemos already means we have, so you do not need to include nosotros unless you want to emphasize it.

I have heard the word carro used for car. Is coche better to use here?

Since you are learning the Spanish spoken in Spain, coche is the most common and natural word for car. Words like carro and auto are widely used in Latin America, but in Spain, a carro usually means a cart or a shopping cart.