De jure, Russian Federation is a semi-presidential republic. According to the Constitution of the Russian Federation (chapter 6 article 112), one of the functions of the prime minister (the Chairman of the Government of the Russian Federation) during formation of the government is to submit the list of candidates for various posts, from which the President then chooses his appointees. Similarly, the Constitution states (chapter 4 article 83e) that the President
shall [...] on the proposal by the Chairman of the Government of the Russian Federation appoint and dismiss deputy chairmen of the Government of the Russian Federation and federal ministers
So yeah, in Russia, the President can only choose whoever his head of the government pre-selected for the particular post. Note that the legislative branch of the state (particularly, the State Duma), has to support the prime minister's appointment, or the President will have to choose someone else. In theory, if Duma majority is in opposition to the President, he could be forced to appoint an opposition-supported prime minister: for example, in 1998, as Yeltsin's support was undercut by an ongoing financial crisis, his own choice, Viktor Chernomyrdin, was rejected by the Duma twice; in case the presiden't candidate is rejected for the third time the parliament is dissolved and general elections are to be held. To avoid this scenario, Yeltsin was forced to accept Duma-supported Yevgeniy Primakov as his prime minister.
The problem is, current Russian political system is dominated by Putin's power base, "United Russia" party - they've held the parliamentary majority for decades at this point. So whatever decisions the President needs to be approved by the Duma pass pretty much automatically; in particular, he gets his first choice for the prime minister, and as a consequence - the candidates that the prime minister will submit for the President's choice are likely to be exactly the people the President wants. Similarly, whenever the President needs to dismiss someone from his post - the prime minister will have that proposal ready. No need changing the rules, when you have everything in place to get what you want by just following their letter...