Usually upon receiving a new rank you get a token for a new ship, but what about when you're at the highest rank (VA or general) I noticed with some my alts I'm a lieutenant commander, and it says I get new ship (I have the same light cruiser I started with) I can requistition new ships, but I either have to pay Zen or Dilithium for them.
VA dont get a new token. So yes, its either buying them with dilithium, zen or fleet ship modules+fleet credits (for fleet ships). The last way is the cheapest with zero zen-costs, since Fleet ship modules can be bought via the exchange. And they are superior to the dilithium ones
level 40 is the last level you get a free ship, after that it's c-store, lock box (which you can buy in the exchange as well) or fleet stuff. On a side note, there are some decent very inexpensive ships you can buy that come from some of the lock boxes that are worth grabbing, and you can also open them at level 40, but will be fine to use at level 50 as well - search the exchange under "reward packs" for Mirror Star Cruiser, Mirror Assault Cruiser, Deep Space Science Vessel and Mirror Recon and you'll find those.
Speaking of tokens, what about the ones you get for coming in 3rd, 2nd, 1st place on a fleet action, it says I get them, but I don't know where to go to have them, they're definitely not going right into my inventory, and for some reason, they don't have an icon when I get them, just a blank space by it's text.