The transition to electric heavy-duty fleets requires coordinated planning of charging infrastructure and grid capacity, yet infrastructure decisions are often made under limited information and uncertain grid capacity. This is a major challenge, since grid expansions can be infeasible, costly, or slow to implement, making early estimates of the required charging capacity essential. This paper introduces a planning framework that links a small set of fleet-level statistics to a mixed integer linear programming (MILP) model that estimates the minimal grid connection capacity required for early-stage fleet electrification planning. A structured survey collects these statistics, which a stochastic assignment process converts into a synthetic fleet for the model to optimize charging schedules against. The methodology is demonstrated through a case study of a Danish grocery retailer's food distribution fleet, spanning a partial electrification level of 33 trips and a full electrification level of 120 trips served by battery electric trucks (BETs), performing a mix of regional and long-haul deliveries. Results show that optimized charging reduces the required grid connection capacity by up to 75% compared to uncoordinated charging. Full electrification still requires this capacity to increase by at least 2.5 times, to 2800 kW, driven primarily by the fleet's shift mix. Under a minimal connection objective, charging depots approach an almost constant load. A battery energy storage system (BESS) adds only marginal further reduction, since BET charging is already tightly packed throughout the day. The proposed method offers a low-data entry point for early-stage planning and is particularly relevant in contexts with limited grid availability or long connection lead times, supporting both grid planning and charging infrastructure design decisions.