Does he have a red face in his icon? If so, one of you denounced the other. You need 5 turns after denouncement to declare a formal war (under Casus Belli in the diplomacy screen).
In a way, you do need culture to get access to Casus Belli. All of them are unlocked when you reach certain civics. In your case, I suggest a Joint War with someone that also dislikes him, since it's unlocked as early as Foreign Trade (right after Code of Laws).
If you really need another CB, you need to reach Diplomatic Service (a Renaissance Era civic). This wil grant you the following CBs:
- Holy War - Available when AI convert one of your cities
- War of Liberation - Available when the AI controls a city from a friend or ally
- War of Reconquest - Available when the AI controls a city you founded
- Protectorate War - Available when the AI controls a City-State
If you
still cannot use those, then you need to wait until Nationalism to unlock Colonial War (when the AI is 2 eras behind you) or Mobilization to unlock War of Territorial Expansion (when you have 2 cities within 10 tiles from 2 enemy cities). Nationalism is in Industrial Era, and Mobilization in the Modern Era.
--
If I might offer advice unrelated to the topic, maybe you should focus a bit more on culture. New governments and policies may be quite strong if timed right. Play a game as Rome to see the impact culture has (newly-founded Roman cities start with a Monument, which really helps Culture even later in the game).