I don't know exactly what you mean by "budget" feature, But I think AWS recently added "advanced payments", where you can recharge your account in advance to pay your invoices, though as I understand you still need a CC to sign up (which will be used if you in case go over your budget) which is a shame.

Also I think Vultr supports prepayments (even using cryptocurrency).

EDIT: Oh it looks like you need to add a cc or paypal nevertheless even if you use crypto.