In general, however:
Don't fall victim to one of the classic dev blunders -- the most famous of which is "don't roll your own crypto" -- but only slightly less well-known is this: "Never write your own billing logic when business is on the line!"
> 1. If re-bill is supposed to be the Nth of each month, that simply means N-1 days after the 1st.
I have a credit card that takes the much simpler approach "Your payment due date is the Nth of each month. N can be any value from 1 to 24."
This seems to basically match your approach 3.
If you ask how I think you should bill ( :p ), do it on a fixed day and don't try to do rebilling at a fixed interval. If the day somebody buys your thing is unsuitable for fixed-date billing, the answer is prorating their first period, not interval billing.
This may have unintended consequences. Some examples we faced around this:
1. Stress on our APIs when 15,000 invoices are created in the span of a couple of minutes. We had to build more queueing mechanisms around this. Some services just can't handle more than 100 calls a second.
2. Getting rate limited by MasterCard
3. Some payment providers thinking we're brute-forcing them
I'm just saying this needs consideration when you reach a certain scale.
Brunei weekends are Friday and Sunday. Those poor folks work Mon-Thurs, and then go back to work Saturday!
For handling the different lengths between the months, I've considered a few approaches.
1. If re-bill is supposed to be the Nth of each month, that simply means N-1 days after the 1st. If that falls into another calendar month, fine. So if someone asks to be billed on the 30th of each month, they will be billed on Jan 30th for January, Mar 2nd for February, Mar 30 for March, and so on. I'd make sure the receipt explicitly says "Re-bill for January", "Re-bill for February", etc., so that bill the see on Mar 2nd hopefully will not confuse them, nor will seeing another bill later that month.
2. If re-bill is supposed to be on the 29th-31st, for February it takes place on the 28th (29th in leap years). For other months, if re-bill is supposed to be on 31st, it takes place on the 30th in April, June, September, and November.
3. If you initially order on day 1-21 of the month, your re-billing is the same day ever month. If you initially order on day 22+, your re-billing is on the same number of days before the end of the month as was your initial order. For example, someone who orders on May 30th would re-bill on the 30th in 31 day months, the 29th in 30 days months, and the 27th in February (28th in leap years). If you ask for a change in fixed billing date, you can do so either as Nth day of the month or Mth day from the end of the month, but N or M must be <= 28.